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

class Solution {
public:
    using ll = long long;
    struct hashing {
        ll mod = 1e9 + 7;
        ll base = 131;
        const string& s;
        vector<ll> hs;
        vector<ll> pow;
        hashing(const string& s, ll mod, ll base)
            : s(s), hs(s.size()), pow(s.size()), mod(mod), base(base) {
            hs[0] = s[0];
            pow[0] = 1ll;
            for (int i = 1; i < s.size(); i++) {
                pow[i] = (pow[i - 1] * base) % mod;
                hs[i] = (hs[i - 1] * base + s[i]) % mod;
            }
        }
        ll operator()(int i, int j) {
            if (!i) {
                return hs[j];
            }
            int k = i - 1;
            return (hs[j] - ((hs[k] * pow[j - k]) % mod) + mod) % mod;
        }
    };
    string longestDupSubstring(string s) {
        // bisect ans len, hash to verify
        vector<hashing> hs{hashing(s, 1e9 + 7, 131),
                           hashing(s, 998244353ll, 131)};
        int l = 0, r = s.size();
        vector<unordered_set<ll>> st(2);
        string ans;
        while (l <= r) {
            int m = (l + r) >> 1;
            if (!m) {
                return ans;
            }
            for (auto& t : st) {
                t.clear();
            }
            for (int i = 0; i + m <= s.size(); i++) {
                int cnt = 0;
                for (int j = 0; j < 2; j++) {
                    ll h = hs[j](i, i + m - 1);
                    if (st[j].find(h) != st[j].end()) {
                        cnt++;
                    }
                    st[j].insert(h);
                }
                if (cnt == 2) {
                    ans = s.substr(i, m);
                    break;
                }
            }
            if (ans.size() == m) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return ans;
    }
};
284900