# number of longest common substrings problem

hv at crypt.org hv at crypt.org
Sat Jun 12 16:26:47 CEST 2004

```"N. J. A. Sloane" <njas at research.att.com> wrote:
: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?
:
:Remarks:
:
:S is a substring of X if S can be
:obtained by deleting some of the entries of X
:
:You can choose any alphabet you like.
:
:Here is a definition of "longest common substring" from
:
:http://www.cs.sunysb.edu/~algorith/files/longest-common-substring.shtml
:
:
: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?

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"?

Hugo van der Sanden

```