Longest Common Subsequence

[huimeich]

Given two strings, find the longest common subsequence (LCS). Example For "ABCD" and "EDCA", the LCS is "A" (or "D", "C"), return 1.

For "ABCD" and "EACB", the LCS is "AC", return 2

class Solution {
public:
    /**
     * @param A, B: Two strings.
     * @return: The length of longest common subsequence of A and B.
     */
    int longestCommonSubsequence(string A, string B) {
        int i,j; int n=A.size(), m=B.size(); 
        vector<vector<int>> p(n+1,vector<int>(m+1,0));
        for (i=1;i<=n;i++) {
            for (j=1;j<=m;j++) {
                p[i][j]=max(p[i][j-1],p[i-1][j]);
                if (A[i-1]==B[j-1]) 
                    p[i][j]=max(p[i][j],p[i-1][j-1]+1);
            }
        }
        return p[n][m];
    }
}

[huimeich]

Longest Common Substring ################################################################## Given two strings, find the longest common substring.

Return the length of it. Example Given A = "ABCD", B = "CBCE", return 2.

Note The characters in substring should occur continuously in original string. This is different with subsequence.

class Solution {
public:    
    /**
     * @param A, B: Two string.
     * @return: the length of the longest common substring.
     */
    int longestCommonSubstring(string &A, string &B) {
        int n=A.size(), m=B.size(); int mx=0;
        if (n==0 || m==0) return 0;
        vector<vector<int>> p(n+1,vector<int>(m+1,0));
        for (int i=1;i<=n;i++) {
            for (int j=1;j<=m;j++) {
                if (A[i-1] == B[j-1]) {
                    p[i][j]=p[i-1][j-1]+1;
                    mx=max(mx,p[i][j]);
                }
            }
        }
        return mx;
    }
};