my earlier program stopped too soon, better: LongestCommonSubstring[keep : {{__} ..}] := Module[{done = False, uit = {}, it = keep, alfa = {1}, z}, While[Intersection @@ it =!= {} && ! done, z = 1; While[ ! (done = ( {0} === (alfa ))) && (alfa = Intersection @@ Take[it, All, {1, z}]) === {}, z++]; If[done, Break[]];(* Print[{z, alfa[[1]]}] *); AppendTo[uit, temp = Flatten[ Thread[w[Take[it, All, {1, z}], alfa[[1]], 1, 1]] /. w -> Position]]; it = Thread[rop[it, temp]] /. rop -> Drop ; it = PadRight[#, Max[Length /@ keep]] & /@ it;(* Print[it] *)]; Drop[Rest@FoldList[Plus, 0, uit], -1]] other lines as before: keep = Table[Random[Integer, {1, 4}], {8}, {36}] soln = LongestCommonSubstring[keep] MapAt[w, keep, Flatten[Transpose[{Range[Length[#]], #}] & /@ soln, 1]] /. w[i_] :> (j = (i - 1)/4.; StyleForm[i, FontColor -> Hue[j, 1, 1], FontWeight -> "Bold"] ) Length @ soln First[keep][[First /@ soln]] W. ----- Original Message ----- From: "N. J. A. Sloane" <njas@research.att.com> To: <seqfan@ext.jussieu.fr>; <math-fun@mailman.xmission.com> Cc: <njas@research.att.com> Sent: Saturday, June 12, 2004 11:17 PM Subject: [math-fun] Re: longest common subsequence - clarification of problem Al Aho tells me that the problem he is interested in is to find the maximum number of longest common subsequences of two sequences X and Y of length n, without regard to where the subsequence occurs in X and Y. So for X = aabaa, Y = aaabb, the length of the lcs is 3, and there are two subsequences of length 3 that are possible, aaa and aab. So here F(X,Y) = 2. Some definitions: S is a subsequence of X if S can be obtained by deleting some of the entries of X (not necessarily adjacent). S is a longest common subsequence of X and Y if S is a subsequence of X, S is a subsequence of Y, and there is no T such that S subsequence of T, S not equal T, and T is a subsequence of X, T is a subsequence of Y. Given sequences X and Y of length n, let LCS(X,Y) be the length of the longest common subsequence. Let F(X,Y) = no of sequences S such that S is a longest common subsequence of X and Y. So S has length LCS(X,Y). Given n, what is the maximal value of F(X,Y) over all choices of X and Y over any alphabet? The version of the problem that i stated earlier, where you also take into account the location of S inside X and Y, is also interesting, it is just not Al's original question. NJAS _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun