I snooped around in http://www.cs.sunysb.edu/~algorith/files/longest-common-substring.shtml and, under header 'Implementations', dived into Combinatorica (Mathematica) (rating 2) only to find the absence of an implementation. This must be the mathematical equivalent of 'vacuum energy', the famous object that is symmetric to anything you throw at it, the ultimate nothingness ? ;-) W. ----- Original Message ----- From: "N. J. A. Sloane" <njas@research.att.com> To: <math-fun@mailman.xmission.com>; <seqfan@ext.jussieu.fr> Cc: <njas@research.att.com> Sent: Saturday, June 12, 2004 5:40 AM Subject: number of longest common substrings problem 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 (not necessarily adjacent). 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 (see also http://www.nist.gov/dads/HTML/longestCommonSubstring.html) 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! NJAS