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

vector<ll> power1, power2;
ll mod1 = INT_MAX - 1e9;
ll mod2 = 999119999;
ll p1 = 257;
ll p2 = 31;

    struct Hash {
        int n;
        string s;
        ll p;
        ll mod;
        vector<ll> pw, hash;

        Hash(string _s, ll pri, ll modd) : s(_s) {
            p = pri;
            mod = modd;
            n = s.size();
            pw.resize(n + 1);
            hash.resize(n + 1);
            pw[0] = 1;
            for (int i = 1; i <= n; i++)
                pw[i] = (pw[i - 1] * p) % mod;
            hash[0] = s[0] - 'a' + 1;
            for (int i = 1; i < n; i++)
                hash[i] = (hash[i - 1] + pw[i] * (s[i] - 'a' + 1)) % mod;
        }

        ll getHash(int l, int r) {
            return (hash[r] - (l ? hash[l - 1] : 0) + mod) % mod;
        }

        bool equal(int l1, int r1, int l2, int r2) {
            if (r1 - l1 != r2 - l2)
                return 0;
            if (l1 > l2)
                swap(l1, l2), swap(r1, r2);
            return (pw[l2 - l1] * getHash(l1, r1) % mod) == getHash(l2, r2);
        }

        bool isPal(int l, int r) { return equal(l, r, n - 1 - r, n - 1 - l); }
    };
    bool check(int len, Hash &hash1, Hash &hash2, string &s) {
        if (len == 0) return true;
        int n = s.size();
        map<long long,int> mp1;
        map<long long, int> mp2;

        for(int i = 0; i <= n - len; i++) {
            int x = (power1[n - len - i] * hash1.getHash(i, i + len - 1)) % mod1;
            int y = (power2[n - len - i] * hash2.getHash(i, i + len - 1)) % mod2;
           
           if (mp1.find(x) != mp1.end() && mp2.find(y) != mp2.end()) {
             return true;
           }

           mp1[x] = 1;
           mp2[y] = 1;
            
        }

        return false;

        

    }
    string longestDupSubstring(string s) {
        int n = s.size();

        int lo = 0;
        int hi = n - 1;
        int ans = 0;

        power1.resize(n + 1);
        power2.resize(n + 1);

        power1[0] = 1;
        power2[0] = 1;
        for (int i = 1; i <= n; i++) {
            power1[i] = (power1[i - 1] * p1) % mod1;
            power2[i] = (power2[i - 1] * p2) % mod2;

        }

        

        Hash hash1 = Hash(s, p1, mod1);
        Hash hash2 = Hash(s, p2, mod2);




        while (lo <= hi) {
            int mid = (lo + hi) / 2;

            if (check(mid, hash1, hash2, s)) {
                lo = mid + 1;
                ans = mid;
            }

            else
                hi = mid - 1;
        }

        if (ans == 0)  return "";

        map<long long,int> mp;

        for(int i = 0; i <= n - ans; i++) {
            int x = (power1[n - ans - i] * hash1.getHash(i, i + ans - 1)) % mod1;
            if(mp.find(x) == mp.end())
               mp[x] = 1;
            
            else return s.substr(i, ans); 
        }

        


        return s;
    }
};
388580