number of longest common substrings problem

N. J. A. Sloane njas at
Sat Jun 12 16:46:04 CEST 2004

Hugo asks:

> Here you introduce the word "different" for the first time. Are two
> substrings "different" if the substrings themselves differ, or is it
> sufficient for the letters of the substring to be drawn from different
> positions in X or Y? Ie given:
>    X = "aabaa", Y = "aaabb"
> are there 1 or 4 occurrences of the LCS "aaa"?

Me:  The latter, I think, since the goal of the question is to
determine how rapidly these numbers can grow.

So in your example, the LCS has length 3, and
there seem to be 10 ways to get 3:

X = aabaa  Y = aaabb
    aab..      aa.b.
    aab..      aa..b
    aab..      a.ab.
    aab..      a.a.b
    aab..      .aab.
    aab..      .aa.b
    aa.a.      aaa..
    aa..a      aaa..
    a..aa      aaa..
    .a.aa      aaa..

so a(5) >= 10.


More information about the SeqFan mailing list