Longest Common Subsequence

Related: LintCode 762 - Longest Common Subsequence II
Dynamic Programming | Set 4 (Longest Common Subsequence) | GeeksforGeeks
Given two sequences, find the length of longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous.

A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”. So a string of length n has 2^n different possible subsequences.
LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3.
1) Optimal Substructure: 
Let the input sequences be X[0..m-1] and Y[0..n-1] of lengths m and n respectively. And let L(X[0..m-1], Y[0..n-1]) be the length of LCS of the two sequences X and Y. Following is the recursive definition of L(X[0..m-1], Y[0..n-1]).

If last characters of both sequences match (or X[m-1] == Y[n-1]) then
L(X[0..m-1], Y[0..n-1]) = 1 + L(X[0..m-2], Y[0..n-2])

If last characters of both sequences do not match (or X[m-1] != Y[n-1]) then
L(X[0..m-1], Y[0..n-1]) = MAX ( L(X[0..m-2], Y[0..n-1]), L(X[0..m-1], Y[0..n-2])

Following is a tabulated implementation for the LCS problem.
http://www.csl.mtu.edu/cs2321/www/pdfslides/Goodrich_6e_Ch13_DynamicProgramming-handouts.pdf

int lcs( char *X, char *Y, int m, int n )

{

   int L[m+1][n+1];

   int i, j;

  

   /* Following steps build L[m+1][n+1] in bottom up fashion. Note

      that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */

   for (i=0; i<=m; i++)

   {

     for (j=0; j<=n; j++)

     {

       if (i == 0 || j == 0)

         L[i][j] = 0;

  

       else if (X[i-1] == Y[j-1])

         L[i][j] = L[i-1][j-1] + 1;

  

       else

         L[i][j] = max(L[i-1][j], L[i][j-1]);

     }

   }

    

   /* L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] */

   return L[m][n];

}

Print Solution:

https://www.jiuzhang.com/solution/longest-common-subsequence/

    public int longestCommonSubsequence(String A, String B) {
        int n = A.length();
        int m = B.length();
        int f[][] = new int[n + 1][m + 1];
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                if(A.charAt(i - 1) == B.charAt(j - 1))
                    f[i][j] = f[i - 1][j - 1] + 1;
            }
        }
        return f[n][m];
    }

http://rosettacode.org/wiki/Longest_common_subsequence#Java

public static String lcs(String a, String b){
    int aLen = a.length();
    int bLen = b.length();
    if(aLen == 0 || bLen == 0){
        return "";
    }else if(a.charAt(aLen-1) == b.charAt(bLen-1)){
        return lcs(a.substring(0,aLen-1),b.substring(0,bLen-1))
            + a.charAt(aLen-1);
    }else{
        String x = lcs(a, b.substring(0,bLen-1));
        String y = lcs(a.substring(0,aLen-1), b);
        return (x.length() > y.length()) ? x : y;
    }
}

DP

public static String lcs(String a, String b) {
    int[][] lengths = new int[a.length()+1][b.length()+1];
 
    // row 0 and column 0 are initialized to 0 already
 
    for (int i = 0; i < a.length(); i++)
        for (int j = 0; j < b.length(); j++)
            if (a.charAt(i) == b.charAt(j))
                lengths[i+1][j+1] = lengths[i][j] + 1;
            else
                lengths[i+1][j+1] =
                    Math.max(lengths[i+1][j], lengths[i][j+1]);
 
    // read the substring out from the matrix
    StringBuffer sb = new StringBuffer();
    for (int x = a.length(), y = b.length();
         x != 0 && y != 0; ) {
        if (lengths[x][y] == lengths[x-1][y])
            x--;
        else if (lengths[x][y] == lengths[x][y-1])
            y--;
        else {
            assert a.charAt(x-1) == b.charAt(y-1);
            sb.append(a.charAt(x-1));
            x--;
            y--;
        }
    }
 
    return sb.reverse().toString();
}

http://www.geeksforgeeks.org/printing-longest-common-subsequence/

   int i = m, j = n;

   while (i > 0 && j > 0)

   {

      // If current character in X[] and Y are same, then

      // current character is part of LCS

      if (X[i-1] == Y[j-1])

      {

          lcs[index-1] = X[i-1]; // Put current character in result

          i--; j--; index--;     // reduce values of i, j and index

      }

      // If not same, then find the larger of two and

      // go in the direction of larger value

      else if (L[i-1][j] > L[i][j-1])

         i--;

      else

         j--;

   }

Space Optimization:
Use one array O(N):  backward
http://www.devhui.com/2015/04/21/Longest-Common-Substring/

int LCS_dp(char * X, int xlen, char * Y, int ylen) {

memset(dp,0,sizeof(dp));

int maxlen =0, maxindex = 0;

for(int i = 0; i < xlen; ++i) {

for(int j = ylen-1; j >= 0; --j) {

if(X[i] == Y[j]) {

if(i && j) {

dp[j] = dp[j-1] + 1;

}

if(i == 0 || j == 0) {

dp[j] = 1;

}

if(dp[j] > maxlen) {

maxlen = dp[j];

maxindex = i + 1 - maxlen;

}

} else {

dp[j] = 0;

}

}

}

int maxlen;

}

Forward, use tmp variable:
http://www.jurieo.com/1064.html

        int lenS1=strlen(s1), lenS2=strlen(s2);

        for(int i=0; i<lenS1; i++){

            old=0;

            //若s1[i]==s2[j], dp[i][j] = dp[i-1][j-1]+1

            //否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])

            //此处进行了空间优化，old 代表 dp[i-1][j-1]

            //dp[j-1] 代表 dp[i][j-1], dp[j] 代表 dp[i-1][j]

            for(int j=0; j<lenS2; j++){

                tmp = dp[j];

                if(s1[i]==s2[j])

                    dp[j] = old+1;

                else

                    if(dp[j-1]>dp[j])dp[j]=dp[j-1];

                old = tmp;

            }

        }

Use two O(N) arrays:
http://www.ics.uci.edu/~eppstein/161/960229.html

    int lcs_length(char * A, char * B)
    {
 allocate storage for one-dimensional arrays X and Y
 for (i = m; i >= 0; i--)
 {
     for (j = n; j >= 0; j--)
     {
  if (A[i] == '\0' || B[j] == '\0') X[j] = 0;
  else if (A[i] == B[j]) X[j] = 1 + Y[j+1];
  else X[j] = max(Y[j], X[j+1]);
     }
     Y = X;
 }
 return X[0];
    }

http://ideone.com/R3lp88

1. int lcs(string x, string y)
2. {
3. int m = x.length();
4. int n = y.length();
5. int curr[n+1], prev[n+1]; // take two array of shorter length to keep track of previous rows
6. for (int i = 0; i <= m; i++) {
7. for (int j = 0; j <= n; j++) {
8. if (i == 0 || j == 0)
9. curr[j] = 0;
10. else {
11. if (x[i-1] == y[j-1])
12. curr[j]= 1 + prev[j-1];
13. else
14. curr[j] = max(prev[j], prev[j-1]);
15. }
16. }
17. for (int start = 0; start <= n; start++)
18. prev[start] = curr[start];
19. }
20. return curr[n];
21. }
22. int wrapperLCS(string x, string y) // to keep a check that always the shorter length string is passed as second parameter
23. {
24. if (x.length() >= y.length())
25. return lcs(x, y);
26. else
27. return lcs(y, x);
28. }

http://www.programgo.com/article/96392147605/

1. int lcs[2][MAXSIZE];  
2. char s1[MAXSIZE],s2[MAXSIZE];  
3.   
4. int LCS()  
5. {  
6.     int i,j,len1,len2;  
7.     int tag=1;  
8.     len1 = strlen(s1);  
9.     len2 = strlen(s2);  
10.     memset(lcs[0],0,len2*sizeof(int));  
11.     lcs[1][0] = 0;  
12.     for(i=1;i<=len1;i++)  
13.     {  
14.         for(j=1;j<=len2;j++)  
15.         {  
16.             if(s1[i-1] == s2[j-1])  
17.                 lcs[tag][j] = lcs[1-tag][j-1] + 1;  
18.             else  
19.                 lcs[tag][j] = max(lcs[1-tag][j],lcs[tag][j-1]);  
20.         }  
21.         tag = 1 - tag;  
22.     }  
23.     return lcs[1-tag][len2];  
24. } 

Memorizing LCS:
http://www.ics.uci.edu/~eppstein/161/960229.html

    int lcs_length(char * AA, char * BB)
    {
 A = AA; B = BB;
 allocate storage for L;
 for (i = 0; i <= m; i++)
     for (j = 0; j <= m; j++)
  L[i,j] = -1;

 return subproblem(0, 0);
    }

    int subproblem(int i, int j)
    {
 if (L[i,j] < 0) {
     if (A[i] == '\0' || B[j] == '\0') L[i,j] = 0;
     else if (A[i] == B[j]) L[i,j] = 1 + subproblem(i+1, j+1);
     else L[i,j] = max(subproblem(i+1, j), subproblem(i, j+1));
 }
 return L[i,j];
    }

http://www.hankcs.com/program/algorithm/implementation-and-application-of-nlp-longest-common-subsequence-longest-common-subsequence-of-java.html
Backward to fronend:

public class LongestCommonSubsequence

{

    public static int compute(char[] str1, char[] str2)

    {

        int substringLength1 = str1.length;

        int substringLength2 = str2.length;

        // 构造二维数组记录子问题A[i]和B[j]的LCS的长度

        int[][] opt = new int[substringLength1 + 1][substringLength2 + 1];

        // 从后向前，动态规划计算所有子问题。也可从前到后。

        for (int i = substringLength1 - 1; i >= 0; i--)

        {

            for (int j = substringLength2 - 1; j >= 0; j--)

            {

                if (str1[i] == str2[j])

                    opt[i][j] = opt[i + 1][j + 1] + 1;// 状态转移方程

                else

                    opt[i][j] = Math.max(opt[i + 1][j], opt[i][j + 1]);// 状态转移方程

            }

        }

        int i = 0, j = 0;

        while (i < substringLength1 && j < substringLength2)

        {

            if (str1[i] == str2[j])

            {

                System.out.print(str1[i]);

                i++;

                j++;

            }

            else if (opt[i + 1][j] >= opt[i][j + 1])

                i++;

            else

                j++;

        }

        System.out.println();

        return opt[0][0];

    }

    public static int compute(String str1, String str2)

    {

        return compute(str1.toCharArray(), str2.toCharArray());

    }

}

http://blog.csdn.net/v_july_v/article/details/6695482

,该算法主要是把求解公共字符串问题转化为求解矩阵L(p,m)的问题，在利用定理求解矩阵的元素过程中（1）while(i<k),L(k,i)=null，
                  （2）while(L(k,i)=k),L(k,i+1)=L(k,i+2)=…L(k,m)=k；

    求出每列元素，一直到发现第p+1 行都为null 时退出循环，得出矩阵L(k,m)后，B[L(1,m-p+1)]B[L(2,m-p+2)]…B[L(p,m)]即为A 和B 的LCS，其中p 为LCS 的长度。

http://www.cnblogs.com/ider/p/longest-common-substring-problem-optimization.html
暴力解法

int longestCommonSubstring_n3(const string& str1, const string& str2)
 2 {   
 3     size_t size1 = str1.size();
 4     size_t size2 = str2.size();
 5     if (size1 == 0 || size2 == 0) return 0;

 7     // the start position of substring in original string
 8     int start1 = -1;
 9     int start2 = -1;
10     // the longest length of common substring 
11     int longest = 0; 
13     // record how many comparisons the solution did;
14     // it can be used to know which algorithm is better
15     int comparisons = 0;
16  
17     for (int i = 0; i < size1; ++i)
18     {
19         for (int j = 0; j < size2; ++j)
20         {
21             // find longest length of prefix 
22             int length = 0;
23             int m = i;
24             int n = j;
25             while(m < size1 && n < size2)
26             {
27                 ++comparisons;
28                 if (str1[m] != str2[n]) break;
29  
30                 ++length;
31                 ++m;
32                 ++n;
33             }
34  
35             if (longest < length)
36             {
37                 longest = length;
38                 start1 = i;
39                 start2 = j;
40             }
41         }
42     }
48     return longest;
49 }

Todo: http://www.csie.ntnu.edu.tw/~u91029/LongestCommonSubsequence.html
Read full article from Dynamic Programming | Set 4 (Longest Common Subsequence) | GeeksforGeeks