image.png
解法一： 暴力枚举，使用两根指针，分别只在两个子串的开头位置
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
if(A.empty() || B.empty()) return 0;
int lcs = 0;
for(int i = 0; i < A.size(); i++){
for(int j = 0; j < B.size(); j++){
int lcs_cur = 0;
while((i+lcs_cur < A.size()) &&
(j + lcs_cur) < B.size() &&
A[i + lcs_cur] == B[j + lcs_cur]){
lcs_cur++;
}
if(lcs_cur > lcs) lcs = lcs_cur;
}
}
return lcs;
}
};
