Hide
Easily highlight source code for your blog with our Syntax Highlighter. Join Siafoo Now or Learn More

LCS Atom Feed 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.