 License Creative Commons Attribution Share Alike 3.0-US
Keywords algorithm (8) lcs (5)
Related 'A' Longest Common Subsequence (LCS) implementation LCS C++ template classes find ALL common subsequences and then sort for longest recursive solution for LCS problem Python Tips, Tricks, and Hacks
Permissions Viewable by Everyone Editable by All Siafoo Users LCS 0

 In Brief Find a longest common subsequence between two sequences.
 Implementation Difficulty     ` 1 Example for character comparison. 2  3 Memoizing LCS: 4  5     char * A; 6     char * B; 7     array L; 8  9     int lcs_length(char * AA, char * BB)10     {11         A = AA; B = BB;12         allocate storage for L;13         for (i = 0; i <= m; i++)14             for (j = 0; j <= m; j++)15                 L[i,j] = -1;16 17         return subproblem(0, 0);18     }19 20     int subproblem(int i, int j)21     {22         if (L[i,j] < 0) {23             if (A[i] == '\0' || B[j] == '\0') L[i,j] = 0;24             else if (A[i] == B[j]) L[i,j] = 1 + subproblem(i+1, j+1);25             else L[i,j] = max(subproblem(i+1, j), subproblem(i, j+1));26         }27         return L[i,j];28     }`

Find a longest common subsequence between two sequences.