Maximum Length of Repeated Subarray

发表于 Waline： 阅读次数： 本文字数： 489 阅读时长 ≈ 1 分钟

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;
    }
};