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

typedef long long ll ; 

const ll mod = 1e15+37 ; 

ll add(ll a, ll b) { return (a + b)  % mod;}
ll mul(ll a, ll b) { return (a * b) % mod;}
ll sub(ll a, ll b) {return (a - b  + mod) % mod;}

class Solution {
public:
    string longestDupSubstring(string s) {
        
        ll low = 1 , high = s.size();
        ll ans = 0 ; 
        ll st = -1; 
        while(low<=high)
        {
            ll mid = (low+high)/2 ; 
            
            bool ok = 0 ; 
            
            unordered_map<ll,ll> allHash ; 
            
            ll p = 31 ;
            ll hash = 0 ;
            for(ll i = mid - 1 ; i>=0 ; --i)
            {
                hash = add(hash, mul(s[i]-'a'+1 , p));
                if(i!=0)p = mul(p,31);
            }
            
            allHash[hash]++;
            ll stt = -1; 
            for(ll i = mid ; i<s.size();++i)
            {
                hash = sub(hash , mul(s[i-mid]-'a'+1 ,p)); 
                hash = mul(hash,31);
                hash = add(hash, mul(s[i]-'a'+1 , 31));
                
                if(allHash.count(hash))
                    ok = 1 , stt = i-mid+1;
                allHash[hash]++;
            }
            
            if(ok)
            {
                ans = max(ans,mid);
                st = stt ; 
                low = mid+1 ; 
            }
            else high = mid-1 ;
        }
        string fans = "";
        if(st!=-1)
            fans = s.substr(st,ans);
        return fans;
    }
};
290660