<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:
    #define ll long long
    const ll mod1=1e9+7;
    const ll mod2=1e9+9;
    ll p1=31;
    ll p2=37;

    ll get_hash(string s,ll p,ll mod){
        ll ans=0;
        for(auto i:s) ans=(ans*p+(i-'a'+1))%mod;
        return ans;
    }
    pair<bool,ll> match(string s,ll len){
        // if (len == 0) return {false, -1};
       set<ll> st1;
       set<ll> st2;
       ll n=s.size();
        
       string str=s.substr(0,len);
       ll hash1=get_hash(str,p1,mod1);
       ll hash2=get_hash(str,p2,mod2);

       ll p_pow1=1,p_pow2=1;
       for(ll i=1;i<len;i++){
         p_pow1=((p_pow1*p1)%mod1);
         p_pow2=((p_pow2*p2)%mod2);
       }

       st1.insert(hash1);
       st2.insert(hash2);

       for(ll l=1,r=len;r<n;l++,r++){
         ll del1=((s[l-1]-'a'+1 )*p_pow1)%mod1;
         ll del2=((s[l-1]-'a'+1 )*p_pow2)%mod2;
         ll add1=(s[r]-'a'+1);
         ll add2=(s[r]-'a'+1);

         hash1=((hash1-del1+mod1)*p1+add1)%mod1;
         hash2=((hash2-del2+mod2)*p2+add2)%mod2;

         if(st1.find(hash1) != st1.end() && st2.find(hash2) != st2.end()) return {1,l};

         st1.insert(hash1);
         st2.insert(hash2);

       }

       return {0,-1};

    }
    string longestDupSubstring(string s) {
        ll l = 0, r = s.size();

        while (l < r) {
            ll mid = l + (r - l) / 2;
            auto it = match(s, mid);
            if (it.first) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }

        if (l == 0) return "";
        auto it = match(s, l - 1);
        return s.substr(it.second, l - 1);
    }
};

451940