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

struct RollingHash {

    int length;
    long long base;
    long long mod;
    vector<long long> hash_list;
    vector<long long> base_mod;

    RollingHash(string str, long long base = 29, long long mod = 1e9 + 9) : length((int) str.size()), base{base}, mod{mod}, hash_list((int) str.size() + 1), base_mod((int) str.size() + 1, 1LL) {

        for (int i = 0; i < (int) str.size(); i++) {
            hash_list[i + 1] = (base * hash_list[i] + (long) int(str[i] - 'a') + 1) % mod;
            base_mod[i + 1] = base_mod[i] * base % mod;
        }
    }

    template<typename T>
    RollingHash(vector<T> vec, long long base = 1e9 + 7, long long mod = 1e9 + 9) : length((int) vec.size()), base{base}, mod{mod}, hash_list((int) vec.size() + 1), base_mod((int) vec.size() + 1, 1LL) {
        for (int i = 0; i < (int) vec.size(); i++) {
            hash_list[i + 1] = (base * hash_list[i] + (long) vec[i]) % mod;
            base_mod[i + 1] = base_mod[i] * base % mod;
        }
    }

    int size() {
        return length;
    }

    long long hash(int left, int right) {
        return (hash_list[right] - (hash_list[left] * base_mod[right - left] % mod) + mod) % mod;
    }

    static int lcp(RollingHash &rh_a, RollingHash &rh_b, int a_left, int b_left) {

        assert (0 <= a_left && a_left < (int) rh_a.size());
        assert (0 <= b_left && b_left < (int) rh_b.size());

        int left = min((int) rh_a.size() - a_left, (int) rh_b.size() - b_left) + 1;
        int right = 0;

        while (1 < (left - right)) {

            int mid = (left + right) / 2;

            if (rh_a.hash(a_left, a_left + mid) != rh_b.hash(b_left, b_left + mid)) {
                left = mid;
            } else {
                right = mid;
            }
        }

        return right;
    }
};


class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {

        int m = nums1.size();
        int n = nums2.size();
        int ans = -1;

        RollingHash rh1{nums1, 103};
        RollingHash rh2{nums2, 103};

        for (int i = 0; i < (int) nums1.size(); i++) {

            for (int j = 0; j < (int) nums2.size(); j++) {

                if (m <= i + ans || n <= j + ans) {
                    break;
                }

                int tmp_ans = RollingHash::lcp(rh1, rh2, i, j);
                ans = max(ans, tmp_ans);
            }
        }

        return ans;
    }
};

14611