Return the length of it.
Example 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.
Notice The characters in substring should occur continuously in original string. This is different with subsequence.
解法1：DP。 DP[i][j]代表以A[i-1]和B[j-1]结尾的LCS。 注意：
不要跟Longest Common Subsequence那题混淆。那题的Subsequence之间可以有间隔，所以要考虑DP[i-1][j]和DP[i][j-1]。这里要用result保存最大值，而Longest Common Subsequence那题最后返回DP[M][N]即可。if的else分支不需要，因为DP[i][j]缺省值为0。DP[][] 的维数为M+1和N+1。代码如下：
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) { int M = A.size(); int N = B.size(); if (M == 0 || N == 0) return 0; vector<vector<int>> DP(M + 1, vector<int>(N + 1, 0)); int result = 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; //} result = max(result, DP[i][j]); } } return result; } };