longest common subsequence - clarification of problem
N. J. A. Sloane
njas at research.att.com
Sat Jun 12 23:17:45 CEST 2004
Al Aho tells me that the problem he is interested in
is to find the maximum number of longest common subsequences
of two sequences X and Y of length n, without regard to
where the subsequence occurs in X and Y.
So for X = aabaa, Y = aaabb, the length of the lcs is 3,
and there are two subsequences of length 3 that are
possible, aaa and aab. So here F(X,Y) = 2.
Some definitions:
S is a subsequence of X if S can be
obtained by deleting some of the entries of X
(not necessarily adjacent).
S is a longest common subsequence of X and Y
if S is a subsequence of X, S is a subsequence of Y, and there
is no T such that S subsequence of T, S not equal T,
and T is a subsequence of X, T is a subsequence of Y.
Given sequences X and Y of length n, let LCS(X,Y) be the
length of the longest common subsequence.
Let F(X,Y) = no of sequences S such that S is a
longest common subsequence of X and Y. So S has length LCS(X,Y).
Given n, what is the maximal value of F(X,Y)
over all choices of X and Y over any alphabet?
The version of the problem that i stated earlier,
where you also take into account the location of S inside X and Y,
is also interesting, it is just not Al's original question.
NJAS
More information about the SeqFan
mailing list