LintCode-最長公共子串

給出兩個字符串，找到最長公共子串。并返回其長度。

您在真實的面試中是否遇到過這個題？?

Yes

例子

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

注意

子串的字符應該連續的出如今原字符串中，這與子序列有所不同。

標簽?Expand??

相關題目?Expand?

分析：注意是子串。不是子序列，當然做法肯定也是動態規劃啦，僅僅只是轉移方程須要略微變化變化。

代碼：

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 hereint n = A.length();int m = B.length();vector<vector<int> > dp(n+1,vector<int>(m+1,0));int ret = 0;for(int i=1;i<=n;i++){char c1 = A[i-1];for(int j=1;j<=m;j++){char c2 = B[j-1];if(c1==c2)dp[i][j] = dp[i-1][j-1]+1;elsedp[i][j] = 0;ret = max(ret,dp[i][j]);}}return ret;}
};