[LintCode]最長共通サブストリング
3412 ワード
1 class Solution {
2 public:
3 /**
4 * @param A, B: Two string.
5 * @return: the length of the longest common substring.
6 */
7 int longestCommonSubstring(string &A, string &B) {
8 // write your code here
9 int m = A.length(), n = B.length(), len = 0;
10 vector<int> cur(m + 1, 0);
11 for (int j = 1; j <= n; j++) {
12 int pre = 0;
13 for (int i = 1; i <= m; i++) {
14 int temp = cur[i];
15 cur[i] = (A[i - 1] == B[j - 1]) ? pre + 1 : 0;
16 pre = temp;
17 len = max(len, cur[i]);
18 }
19 }
20 return len;
21 }
22 };