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

using lli=long long;
struct Hasher{
    lli n,p,m;
    vector<lli>fhash;
    vector<lli>powk;
    void init(string &s,int _p,int _m)
    {
        p=_p;
        m=_m;
        n=s.size();
        fhash.resize(n);
        powk.resize(n);
        powk[0]=1;
        fhash[0]=((s[0]-'a')+1);
        for(int i=1;i<n;i++)
        {
            fhash[i]=(((fhash[i-1]*p)%m)+((s[i]-'a')+1))%m;
            powk[i]=(powk[i-1]*p)%m;
        }

    }
    int getfhash(int l,int r)
    {
        if(l==0)
        {
            return fhash[r];
        }
        lli ans=((fhash[r]-((fhash[l-1]*powk[r-l+1])%m))%m + m)%m;
        return ans;

    }
};
struct doubleHasher{
    Hasher a,b;
    void init(string &s)
    {
        int n=s.size();
        a.init(s,31,999999929);
        b.init(s,37,999999937);
    }
    pair<int,int> gethash(int l,int r)
    {
        return make_pair(a.getfhash(l,r),b.getfhash(l,r));
    }

};

class Solution {
public:
    doubleHasher ha;
    string finalans;
    int check(int mid,int n,string &s)
    {
        map<pair<int,int>,int>mp;
        map<pair<int,int>,int>indexhash;
        for(int i=0;i+mid-1<n;i++)
        {
            mp[ha.gethash(i,i+mid-1)]++;
            indexhash[ha.gethash(i,i+mid-1)]=i;
        }
        int fl=0;
        int indx=-1;
        for(auto v:mp)
        {
            if(v.second>=2)
            {
                fl=1;
                indx=indexhash[v.first];
                break;
            }
        }
        if(fl)
        {
            finalans=s.substr(indx,mid);
        }
        return fl;
    }
    string longestDupSubstring(string s) {
        int n=s.size();
        ha.init(s);
        int lo=1;
        int hi=n;
        int ans=0;
        while(lo<=hi)
        {
            int mid=(lo+hi)/2;
            if(check(mid,n,s))
            {
                ans=mid;
                lo=mid+1;
            }
            else
            {
                hi=mid-1;
            }
        }
        if(ans==0)
        {
            return "";
        }
       
        return finalans;
    }
};
394340