<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:
    vector<long long int> hash;
    vector<long long int> base;
    vector<long long int> hasha;
    vector<long long int> basea;
    int mod = 1e9+7;
    Solution(){
        hash = vector<long long int> (30001,0);
        base = vector<long long int> (30001,0);
        hasha = vector<long long int> (30001,0);
        basea = vector<long long int> (30001,0);
    }
    void init(string w){
        int n = w.length();
        base[0]=1;
        hash[0]=w[0]-'a'+1;
        for(int i=1;i<n;i++){
            base[i]=(31*base[i-1])%mod;
            hash[i]=(hash[i-1]*31+(w[i]-'a'+1))%mod;
        }
        basea[0]=1;
        hasha[0]=w[0]-'a'+1;
        for(int i=1;i<n;i++){
            basea[i]=(29*basea[i-1])%mod;
            hasha[i]=(hasha[i-1]*29+(w[i]-'a'+1))%mod;
        }
    }
    long long int get_value(int start,int end){
        long long int diff = base[end-start+1];
        long long int begin = 0 ;
        if(start>0){begin=hash[start-1];}
        long long int ans = (hash[end]-(begin*diff)%mod)%mod;
        if(ans<0){ans=ans+mod;}
        return ans;
    }
    long long int get_valuea(int start,int end){
        long long int diff = basea[end-start+1];
        long long int begin = 0 ;
        if(start>0){begin=hasha[start-1];}
        long long int ans = (hasha[end]-(begin*diff)%mod)%mod;
        if(ans<0){ans=ans+mod;}
        return ans;
    }
    long long int check(int len,string w){
        int n=w.length();
        map<long long int,long long int> rep;
        map<long long int,long long int> repa;
        for(int i=0;i+len<n;i++){
            long long int num = get_value(i,i+len);
            long long int numa = get_valuea(i,i+len);
            if(rep[num]>0 && repa[numa]>0){
                return i;
            }
            rep[num]++;
            repa[numa]++;
        }
        return -1;
    }
    string longestDupSubstring(string s) {
        int l=1,r=s.length();
        string ans="";
        init(s);
        while(l<=r){
            int mid=l+(r-l)/2;
            int num = check(mid-1,s);
            cout<<l<<" "<<mid<<" "<<num<<" "<<r<<endl;
            if(num!=-1){
                ans=s.substr(num,mid);
                l=mid+1;
                
            }else{
                r=mid-1;
            }
        }
        return ans;
    }
};
371300