**Know what you're getting**– Unlike many sites, all our code is clearly licensed. Join Siafoo Now or Learn More

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

Add a Comment