<p>Given a string <code>s</code>, consider all <em>duplicated substrings</em>: (contiguous) substrings of s that occur 2 or more times.&nbsp;The occurrences&nbsp;may overlap.</p>

<p>Return <strong>any</strong> duplicated&nbsp;substring that has the longest possible length.&nbsp;If <code>s</code> does not have a duplicated substring, the answer is <code>&quot;&quot;</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> s = "banana"
<strong>Output:</strong> "ana"
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> s = "abcd"
<strong>Output:</strong> ""
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= s.length &lt;= 3 * 10<sup>4</sup></code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
</ul>

#define D1(x) cout << (#x) << " = " << x << endl;
#define D2(x, y) cout << (#x) << " = " << x << (#y) << y << endl;
#define FOR(i, a, b) for (int i = a; i < b; ++i)
template<class X, class Y> void Max(int& x, int y) {}

class Solution {
public:
    using ll = long long;
    string longestDupSubstring(string s) {
        constexpr ll P1 = 31;
        constexpr ll M1 = 1'000'000'007;
        constexpr ll P2 = 37;
        constexpr ll M2 = 1'000'000'009;
        int n = s.size();
        vector<ll> a(n, 0);
        FOR(i,0,n) {
            a[i] = s[i] - 'a' + 1;
        }
        int l = 0;  // always correct.
        int r = n;  // always incorrect.
        string ans = "";
        while (l + 1 < r) {
            int m = (l + r) / 2;
            // D1(m);
            ll h1 = 0, h2 = 0, p1 = P1, p2 = P2;
            for (int i = 0; i < m - 1; ++i) {
                h1 = (h1 * P1 + a[i] * P1) % M1;
                h2 = (h2 * P2 + a[i] * P2) % M2;
                p1 = (p1 * P1) % M1;
                p2 = (p2 * P2) % M2;
            }
            unordered_set<ll> s1, s2;
            bool ok = false;
            for (int i = 0; i <= n - m; ++i) {
                // add the new term.
                h1 = (h1 * P1 + a[i + m - 1] * P1) % M1;
                h2 = (h2 * P2 + a[i + m - 1] * P2) % M2;
                // cout << " i = " << i << ", h1 = " << h1 << ", h2 = " << h2 << endl;
                if (s1.find(h1) != s1.end() && s2.find(h2) != s2.end()) {
                    ok = true;
                    ans = s.substr(i, m);
                    break;
                }
                s1.insert(h1);
                s2.insert(h2);
                // prepare for next.
                for (h1 -= a[i] * p1; h1 < 0; h1 += M1);
                h1 %= M1;
                // D1(h1);
                // assert(h1 >= 0);
                // while (h1 < 0) h1 = (h1 + M) % M1;
                for (h2 -= a[i] * p2; h2 < 0; h2 += M2);
                h2 %= M2;
                // D1(h2);
                // assert(h2 >= 0);                
            }
            if (ok) {
                l = m;
            } else {
                r = m;
            }
        }
        return ans;
    }
};
405860