79-最长公共子串
思路
参考博客http://blog.csdn.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;
}
};