<p>Given two integer arrays <code>nums1</code> and <code>nums2</code>, return <em>the maximum length of a subarray that appears in <strong>both</strong> arrays</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
<strong>Output:</strong> 3
<strong>Explanation:</strong> The repeated subarray with maximum length is [3,2,1].
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
<strong>Output:</strong> 5
<strong>Explanation:</strong> The repeated subarray with maximum length is [0,0,0,0,0].
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums1.length, nums2.length &lt;= 1000</code></li>
	<li><code>0 &lt;= nums1[i], nums2[i] &lt;= 100</code></li>
</ul>

#include <iostream>

using namespace std;

class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        const int P = 113;
        const int MOD = 1e9 + 7;
        const int Pinv = powMod(P, MOD - 2, MOD);  // Modular inverse of P

        auto rolling = [&](const vector<int>& arr, int length) {
            vector<pair<int, int>> result;
            if (length == 0) {
                result.push_back({0, 0});
                return result;
            }

            long long int h = 0, power = 1;
            for (int i = 0; i < arr.size(); i++) {
                h = (h + arr[i] * power) % MOD;
                if (i < length - 1) {
                    power = (power * P) % MOD;
                } else {
                    result.push_back({h, i - (length - 1)});
                    h = (h - arr[i - (length - 1)]) * Pinv % MOD;
                    if (h < 0) h += MOD;
                }
            }
            return result;
        };

        auto check = [&](int guess) {
            unordered_map<int, vector<int>> hashes;
            for (auto [ha, start] : rolling(A, guess)) {
                hashes[ha].push_back(start);
            }
            for (auto [ha, start] : rolling(B, guess)) {
                auto it = hashes.find(ha);
                if (it != hashes.end()) {
                    for (int i : it->second) {
                        if (equal(A.begin() + i, A.begin() + i + guess, B.begin() + start)) {
                            return true;
                        }
                    }
                }
            }
            return false;
        };

        int lo = 0, hi = min(A.size(), B.size()) + 1;
        while (lo < hi) {
            int mi = lo + (hi - lo) / 2;
            if (check(mi)) {
                lo = mi + 1;
            } else {
                hi = mi;
            }
        }
        return lo - 1;
    }

private:
    int powMod(int base, int exp, int mod) {
        int result = 1;
        while (exp > 0) {
            if (exp % 2 == 1) {
                result = (1LL * result * base) % mod;
            }
            base = (1LL * base * base) % mod;
            exp /= 2;
        }
        return result;
    }
};
25906