# 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

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

```