718. Maximum Length of Repeated Subarray

这个题要看数的范围能不能用rolling hash，不行的话就得用dp
bisection+rolling hash O((m + n)log(min(m, n))) time O(m + n) space
思路就是二分可能的非法结果，找到第一个（最小的）非法结果，即能找到最大的合法结果，对每个非法结果（长度），分别枚举两个数组的子数组进行比对，这里引入rolling hash来加速，即把第一个数组的指定长度的子数组的rolling hash记录下来，再分别计算第二个数组的子数组的rolling hash值进行比对，如果能找到一致的值再挨个比对两个子数组的每个数

class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        m = A.size(), n = B.size();
        int lo = 1, hi = min(m, n) + 1; // find first INVALID length，因为可能的合法结果是从0到min(m, n)，所以不合法结果的范围整体偏移1，目的是方便写二分，如果正常二分枚举合法结果，最后要不死循环，要不就得最后单独再判断一次
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (isValid(A, B, mid)) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo - 1;
    }

    bool isValid(const vector<int> &A, const vector<int> &B, int len) {
        long hi_pow = 1, ah = 0, bh = 0;
        for (int i = 0; i < len - 1; ++i) { // 这里求的是base的len - 1次方
            hi_pow = hi_pow * base % M;
            ah = (ah * base + A[i]) % M;
            bh = (bh * base + B[i]) % M;
        }
        unordered_map<long, vector<int>> table;
        for (int i = len - 1; i < m; ++i) {
            if (i >= len) {
                ah = (ah + (M - A[i - len]) * hi_pow) % M; // 这里为了避免产生负数要单独处理
            }
            ah = (ah * base + A[i]) % M;
            table[ah].push_back(i - len + 1);
        }
        for (int i = len - 1; i < n; ++i) {
            if (i >= len) {
                bh = (bh + (M - B[i - len]) * hi_pow) % M;
            }
            bh = (bh * base + B[i]) % M;
            if (table.count(bh)) {
                for (int j : table[bh]) {
                    int k = 0;
                    for (; k < len; ++k) {
                        if (A[j + k] != B[i - len + 1 + k]) break;
                    }
                    if (k == len) return true;
                }
            }
        }
        return false;
    }

    int m, n, M = INT_MAX, base = 100; // 这道题所有数都小于100，否则不能这么用
};

dp O(mn) time O(mn) space

class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        int m = A.size(), n = B.size();
        vector<vector<int>> f(m + 1, vector<int>(n + 1));
        int res = 0;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (A[i - 1] == B[j - 1]) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                }
                res = max(res, f[i][j]);
            }
        }
        return res;
    }
};