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

struct hasher
{
    long long m;  
    long long b; 
    string s; 
    long long n;
    vector<long long> pref, pows; 
    hasher(string s, int m, int b): s(s), b(b), m(m){
        n = s.size(); 
        pref.resize(n+1); 
        pows.resize(n+1); 
        pref[0] = 0; 
        pows[0] = 1; 
        for(long long i=1; i<=n; i++) {
            pref[i] = ((b * pref[i-1])%m + (s[i-1]-'a'+1))%m; 
            pows[i] = (pows[i-1] * b)%m;
        }
    }
    long long get(long long l, long long r) {
        l++; r++;
        return (pref[r] - (pref[l-1] * pows[r-l+1])%m + m)%m; 
    }
}; 

class Solution {
public:
    string longestDupSubstring(string s) {
        int n = s.size(); 
        hasher h1(s, 1e9+7, 31), h2(s, 1e9+9, 53);

        int l = 1, r = n-1; 
        int ans = 1;
        string ret = ""; 
 
        while(l<=r) {
            int mid = (l+r)/2; 
            int f = 0;
            int idx = 0; 

            map<long long, int> mp1;
            map<long long, int> mp2;

            for(int i=0; i+mid-1<n; i++){
                if(mp1.find(h1.get(i, i+mid-1)) != mp1.end()){
                    if(mp2.find(h2.get(i, i+mid-1)) != mp2.end())
                    {
                        f = 1;
                        idx = i; 
                        break; 
                    }
                }
                mp1[h1.get(i, i+mid-1)] = 1; 
                mp2[h2.get(i, i+mid-1)] = 1; 
            }

            if(f) {
                l = mid+1;
                cout << mid << endl; 
                ret = s.substr(idx, mid); 
            }
            else {
                r = mid-1; 
            }
        }

        return ret; 
    }
};
377060