<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>v,v2;
    unordered_map<long long,int>mq;
    long long powerwithmod(long long a,long long b)
    {
        long long ans=1;
        long long mod=1e9+7;
        while(b)
        {
            if(b&1)
            {
                ans*=a;
                ans%=mod;
            }
            a=a*a;
            a%=mod;
            b=b>>1LL;
        }
        return ans%mod;
    }


    int solve(int x)
    {
        long long hash=0;
        long long hash2=0;
        long long mod=1e9+7;
        for(int i=0;i<x;i++)
        {
            hash+=v[i];
            hash%=mod;
            hash2+=v2[i];
            hash2%=mod;
        }

        unordered_map<long long,long long>m,m2;
        long long val=67;
        long long val2=31;
        m[hash]++;
        m2[hash2]++;

        for(int i=x;i<int(v.size());i++)
        {
            hash-=v[i-x];
            hash+=v[i];
            hash+=mod;
            hash%=mod;
            long long temp=hash*powerwithmod(val,mod-2);
            temp%=mod;
            m[temp]++;


            hash2-=v2[i-x];
            hash2+=v2[i];
            hash2+=mod;
            hash2%=mod;
            long long temp2=hash2*powerwithmod(val2,mod-2);
            temp2%=mod;
            m2[temp2]++;

            if(m[temp]>1&&m2[temp2]>1)return i-x+1;
            val2=val2*31LL;
            val2%=mod;

            val=val*67LL;
            val=val%mod;
        }
        return 0;
    }


    string longestDupSubstring(string s) {
        long long val=67;
        long long val2=31;
        int mod=1e9+7;
        
        for(int i=0;i<s.size();i++)
        {
            long long hash=0;
            hash+=(s[i]-'a'+1)*val;
            hash%=mod;
            val=val*67LL;
            val%=mod;
            v.push_back(hash);

            long long hash2=0;
            hash2+=(s[i]-'a'+1)*val2;
            hash2%=mod;
            val2=val2*31LL;
            val2%=mod;
            v2.push_back(hash2);
        }

        int l=1,r=s.size()-1;
        int ans=0;
        int valind=0;

        while(l<=r)
        {
            long mid=(l+r)>>1;
            int value=solve(mid);
            if(value>0)
            {
                valind=value;
                ans=mid;
                l=mid+1;
            }
            else{
                r=mid-1;
            }
        }
        string temp="";
        for(int i=valind;i<valind+ans;i++){
            temp.push_back(s[i]);
        }
        return temp;
    }
};


static bool     _foo = ios::sync_with_stdio(false);
static ostream* _bar = cin.tie(NULL);

457700