Maximum Length of Repeated Subarray

Maximum Length of Repeated Subarray

Desc: 给出两个字符串求两串最大公共子串的长度

DP:

dp[i][j]代表了以a[i]b[i]为起点的的字符串的最大公共子串的长度

那么dp[i][j] = a[i] == b[j] ? 1 + dp[i + 1][j + 1] : 0

考虑利用“滚动数组优化”可以降低一维

My_Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int findLength(vector<int>& a, vector<int>& b) {
int m = a.size(), n = b.size();
if (!m || !n) return 0;
vector<int> dp(n + 1);
int res = 0;
for (int i = m - 1; i >= 0; i--) {
for (int j = 0; j < n; j++) {
res = max(res, dp[j] = a[i] == b[j] ? 1 + dp[j + 1] : 0);
}
}
return res;
}
};