Longest common subsequence : Dynamic programming

m: A B C B D A B
yn: B D C A B A

The LCS is B C B A

For arbitrary inputs, it is NP-hard. For constant inputs, DP gives the solution in polynomial time ex: O(n^k). Also, there can be more than one LCSs and the solution for that is exponential time ex: O(k^n).

Here we maintain an LCS matrix of m*n size. Initially, for i= 0 or j = 0, LCSij = 0. Then we use the following optimal substructure.

LCSij = 0                                        for i = 0 or j = 0
          = LCS[i-1,j-1] + 1                for x[i] = y[j]
          = max(LCS[i-1,j],LCS[i , j-1])      for x[i] != y[j]

I thought of the following on my try which also works:

Below is an example from wiki:

| 0 1 2 3 4 5 6 7 | _M_ _Z_ _J_ _A_ _W_ _X_ _U_ ----|----------------- 0 | 0 0 0 0 0 0 0 0 1 _X_ | 0 0 0 0 0 0 1 1 2 _M_ | 0 1 1 1 1 **1 1** 1 3 _J_ | 0 1 1 2 2 **2 2** 2 4 _Y_ | 0 1 1 **2 2** 2 2 2 5 _A_ | 0 1 1 **2 3** 3 3 3 6 _U_ | 0 1 1 2 3 3 3 4 7 _Z_ | 0 1 2 2 3 3 3 4
So the length of the longest subsequence is 4.

**getLongestCommonSubsequence**(x, y): int lcs[m,n] ; //2 d array for i = 0 to m: lcs[i,0] = 0 for j = 0 to n: lcs[0,j] = 0 for i = 1 to m: for j = 1 to n: if x[i] = y[j]: lcs[i,j] = lcs[i-1,j-1] + 1 else: lcs[i,j] = max(lcs[i-1,j], lcs[i,j-1])

After LCS matrix is calculated in O(n*m) time, we just need to trace back from LCS[n,m] location.

**printLCS**(lcs, x, y, i, j): if i = 0 or j = 0: return "" else: if x[i] = y[j]: return printLCS(lcs, x, y, i-1, j-1) + x[i] else: if lcs[i,j-1] > lcs[i-1,j]: return printLCS(lcs, x, y, i, j-1) else: return printLCS(lcs, x, y, i-1, j)

There can be more than one LCS of the same length. The above would print one of them in O(n+m) time. So by DP, we get one LCS in O(n*m) time.

Step by step example

See also