Longest Common Subsequence

by Sujai Kumar
Based on the description in "Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology" by Dan Gusfield.

<< DiscreteMath`Combinatorica`

lcs[lis1_, 
        lis2_] := 
(
lis = 
          Flatten[Sort[Flatten[Position[lis2, #]], Greater] & /@ 
              lis1]; 
new = 
          MapThread[
            List, {lis, 
              Range[Length[lis]]}]; 
ruleset = Rule @@ 
                Reverse[#] & /@ 
            new; 
lis2[[LongestIncreasingSubsequence[Sort[new][[All, 2]]] /. ruleset]]
)

lis1 = 
        Characters["find the longest common but similar \
subsequence"];
lis2 = 
      Characters["find one of the longest common smelly substrings"]; 
    lcs[lis1, lis2] // Timing

lis1 = 
      Characters["find the longest common but similar subsequence"]

Lis1  =  
        Flatten[CellularAutomaton[30, {{1}, 0}, 
            5]];
Lis2 =  
        Flatten[CellularAutomaton[110, {{1}, 0}, 
            5]];
lcs[Lis1, Lis2] // Timing