License Creative Commons Attribution Share Alike 3.0-US
##### Keywords
algorithm (8) lcs (5)
##### Permissions
Viewable by Everyone
Editable by All Siafoo Users
Writing an article is easy - try our reStructured Text demo

# 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.