lintcode-79-最长公共子串

79-最长公共子串

给出两个字符串，找到最长公共子串，并返回其长度。

注意事项

子串的字符应该连续的出现在原字符串中，这与子序列有所不同。

样例

给出A=“ABCD”，B=“CBCE”，返回 2

挑战

O(n x m) time and memory.

标签

字符串处理 LintCode 版权所有

思路

参考博客http://blog.****.net/hackbuteer1/article/details/6686931

与最长公共子序列相似，利用动态规划，动态转移方程为：

• 如果xi == yj， 则 c[i][j] = c[i-1][j-1]+1
• 如果xi ! = yj, 那么c[i][j] = 0

code

class Solution {
public:
    /**
     * @param A, B: Two string.
     * @return: the length of the longest common substring.
     */
    int longestCommonSubstring(string &A, string &B) {
        // write your code here
        int sizeA = A.size(), sizeB = B.size(), i = 0, j = 0;
        int maxLen = 0;

        if(sizeA <= 0 || sizeB <= 0) {
            return 0;
        }

        vector<vector<int> > dpMatrix;
        dpMatrix.resize(sizeA+1);
        for(i=0; i<=sizeA; i++) {
            dpMatrix[i].resize(sizeB+1);
        }
        for(i=0; i<=sizeA; i++) {
            for(j=0; j<=sizeB; j++) {
                dpMatrix[i][j] = 0;
            }
        }

        for(i=1; i<=sizeA; i++) {
            for(j=1; j<=sizeB; j++) {
                if(A[i-1] == B[j-1]) {
                    dpMatrix[i][j] = dpMatrix[i-1][j-1] + 1;
                }
                else {
                    dpMatrix[i][j] = 0;
                }
                maxLen = maxLen >= dpMatrix[i][j] ? maxLen : dpMatrix[i][j];
            }
        }

        return maxLen;
    }
};