LintCode (79) Longest Common Substring Show result

Given two strings, find the longest common substring.

Return the length of it.

Have you met this question in a real interview? 

Yes

Example

Given A = "ABCD", B = "CBCE", return 2.

Note

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

Challenge

O(n x m) time and memory.

这玩意一看就是2D dp,两个串，比比求最长啥啥啥。。。和LCS不一样的是这玩意求得是连续的，所以根本不用管f[i][j-1]和f[i-1][j]， 裸扫一遍完事

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

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 m=A.size(); int n=B.size(); if (m==0 || n==0) return 0; vector< vector<int> > f(m+1, vector<int>(n+1, 0)); int result= INT_MIN; for (int i=1; i<=m; i++){ for (int j=1; j<=n; j++){ if (A[i-1]==B[j-1]) f[i][j]=f[i-1][j-1]+1; result=max(result, f[i][j]); } } return result; } };