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:

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