<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;
    const ll mod1 = 1E9 + 7;  // Changed modulus to a more common prime
    const ll mod2 = 1E9 + 9;  // Changed modulus to a more common prime
    const int p1 = 31;
    const int p2 = 37;
    vector<ll> power1, inver1;
    vector<ll> power2, inver2;
    vector<ll> compute(string& str, vector<ll>& power, ll mod) {
        int n = str.size();
        vector<ll> hash(n);
        hash[0] = (str[0] - 'a');
        for (int i = 1; i < n; i++) {
            hash[i] = (hash[i - 1] + (str[i] - 'a') * power[i]) % mod;
        }
        return hash;
    }

    ll exp(ll n, ll m, ll mod) {
        ll res = 1;
        while (m) {
            if (m % 2) {
                res = (res * n) % mod;
            }
            n = (n * n) % mod;
            m /= 2;
        }
        return res;
    }

    pair<ll, ll> query(vector<ll>& pref1, vector<ll>& pref2, int l, int r) {
        // cout<<r<<endl;
        ll hash1 = (pref1[r] - ((l > 0) ? pref1[l - 1] : 0) + mod1) % mod1;
        hash1 = (hash1 * inver1[l]) % mod1;
        ll hash2 = (pref2[r] - ((l > 0) ? pref2[l - 1] : 0) + mod2) % mod2;
        hash2 = (hash2 * inver2[l]) % mod2;

        return {hash1, hash2};
    }

    bool ok(int x, vector<ll>& pref1, vector<ll>& pref2) {
        set<pair<ll, ll>> got;
        int n = pref1.size();
        for (int i = 0; i + x - 1 < n; i++) {
             if(i+x-1 < 0) continue;
            auto h = query(pref1, pref2, i, i + x - 1);
            if (got.count(h)) {
                return true;
            }
            got.insert(h);
        }
        return false;
    }

    string longestDupSubstring(string str) {
        int n = str.size();
        power1.resize(n), power2.resize(n);
        inver1.resize(n), inver2.resize(n);
        
        power1[0] = 1;
        inver1[0] = 1;
        power2[0] = 1;
        inver2[0] = 1;

        for (int i = 1; i < n; i++) {
            power1[i] = (power1[i - 1] * p1) % mod1;
            power2[i] = (power2[i - 1] * p2) % mod2;
            inver1[i] = exp(power1[i], mod1 - 2, mod1);
            inver2[i] = exp(power2[i], mod2 - 2, mod2);
        }

        vector<ll> pref1 = compute(str, power1, mod1);
        vector<ll> pref2 = compute(str, power2, mod2);

        int l = 0, r = n, bestStart = 0;
        int len = 0;
        while (l <= r) {
            int m = (l + r) / 2;
            if (ok(m, pref1, pref2)) {
                len = m;
                l = m + 1;
            } else {
                r = m - 1;
            }
        }

        if (len == 0) return "";

        set<pair<ll, ll>> seen;
        for (int i = 0; i + len <= n; ++i) {
            auto h = query(pref1, pref2, i, i + len - 1);
            if (seen.count(h)) {
                return str.substr(i, len);
            }
            seen.insert(h);
        }

        return "";
    }
};

256100