LintCode 79. Longest Common Subs

题目链接

Description
  Given two strings, find the longest common substring. Return the length of it.

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

Example1:

Example 1:
Input: "ABCD" and "CBCE"
Output: 2
Explanation:
Longest common substring is "BC"

Example 2:

Input: "ABCD" and "EACB"
Output: 1
Explanation:
Longest common substring is 'A' or 'C' or 'B'

Challenge: O(n x m) time and memory.

思路：
  这是一个经典的动态规划题，定义dp矩阵，dp[i][j]表示A串匹配到i，B串匹配到j时的最大公共长度。dp有A.length()+1行，有B.length()列。第一行与第一列都为0；有状态转移方程
      dp[i][j]=dp[i-1][j-1]+1 ,A[i]==B[j]
      dp[i][j]=0 ,A[i]!=B[j]
最后返回dp的最大值即为最长公共子串长度，代码如下：

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

类似题目：

• 77. Longest Common Subsequence