#define ll unsigned long long int
#define p 31
#define hell 188748146801

class Solution {
public:

    ll power(ll x,ll n)
{
    if(n==0)
        return 1;
    if(n%2==0)
        return power((x*x)%hell,n/2)%hell;
    else
        return (x*(power((x*x)%hell,n/2)%hell))%hell;
}

    ll check(string &s,ll k)
    {
    /*mp stores the hash value and ending index of corresponding hash value\
     i.e the ending index of the substring*/
    unordered_map <ll,ll> mp;
    ll h=0;
    //for rolling hash
    ll pp=power(p,k-1);
    for(ll i=0;i<k;i++)
        h=(h*p+s[i]-'a'+1)%hell;
    mp[h]=k-1;
    for(ll i=k;i<s.length();i++)
    {
        h=(h-pp*(s[i-k]-'a'+1)+hell)%hell;
        h=(h*p+s[i]-'a'+1)%hell;
        /* if the starting point of current susbtring is greater
            than the ending point of previously seen hash then this string is repeating
        */
        if(mp.count(h))
            return mp[h]-k+1;
        mp[h]=i;
    }
    return -1;
}

    string longestDupSubstring(string s) {
        if(s.length()==0)
            return "";
        int l,h,m,ans,id;
        l=0;
        h=s.length();
        ans=0;
        while(l<=h){
            m=l+(h-l)/2;
            int c=check(s,m);
            if(c!=-1){
                ans=m;
                id=c;
                l=m+1;
            }
            else
                h=m-1;
        }
      //  cout<<ans<<"\n";
        if(ans==0)
            return "";
        return s.substr(id,ans);
    }
};