longest common subsequence

[Edwin Clark]

Here's a related sequence that I just submitted. Perhaps someone can add 
more terms or even find a formula:

%I A000001
%S A000001 1, 2, 2, 2, 3, 3, 4, 6, 6, 7, 7, 8
%N A000001 The maximum number of longest common substrings of two binary 
sequences of length n.
%C A000001 A substring of a string is a subsequence of contiguous symbols 
in the string. For example, 00 is a substring of 001 but not of 010.  
Also, for this sequence we do not count the multiplicity of occurrence of 
common substrings.

This is a variation of the problem of Al Aho raised by Neil Sloane on the 
mailing list seqfans. If one replaces "substring of a sequence" in the 
above  by "subsequence of a string" one obtains Aho's problem. In a 
subsequence of a string, the elements need not be contiguous. So that 00 
is a subsequence of both 001 and 010.
%e A000001 a(7) = 4 since the two strings 0001011 and 0011010 have as 
maximum length 
common substrings the 4 strings 011,001,101,010, and computer search 
shows 
that no other pair of strings of length 7 has more than 4 common maximum 
length substrings.
%O A000001 1
%K A000001 ,hard,more,nonn,
%A A000001 W. Edwin Clark (eclark at math.usf.edu), Jun 12 2004



----Edwin