number of longest common substrings problem

N. J. A. Sloane njas at
Sat Jun 12 05:40:53 CEST 2004

I ran into my old friend Al Aho today for
the first time in many years, and he mentioned
the following possibly unsolved problem.

Given two strings X and Y of length n from some fixed
alphabet, let f(X,Y) = number of longest common substrings of X and Y.
What is a(n) = max f(X,Y) over all choices of X and Y?


S is a substring of X if S can be
obtained by deleting some of the entries of X
(not necessarily adjacent).

You can choose any alphabet you like.

Here is a definition of "longest common substring" from

(see also

Given two strings X and Y,
what is the longest string S such that the characters of S appear
as a scattered subsequence of both X and Y?

Then the question is, how many different longest common substrings
can occur?

If someone would compute the initial terms,
we could look it up in the OEIS and see if it a solved problem!


More information about the SeqFan mailing list