<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:
    string longestDupSubstring(string s) {

     int len = s.size();
     // binary search from mid
     function<string(int)> rabinKarp;
     int mod = 1e7+7;
     
     //pre cal pow
     vector<int>powerz(len);
     powerz[ 0 ] = 1;
     for(int i = 1; i < len; i++){
        powerz[ i ] = (powerz[ i - 1 ] *2 )%mod; 
     }

     rabinKarp = [&](int mid){
         if(mid==0)return string("");
         unordered_map<int,vector<int>> rollingHash;
         int cur = 0; 
         for(int i = 0; i < mid; i++){
              cur = (cur * 2 + (s[i]-'a'))%mod;
         }
         rollingHash[ cur ] = {0}; 
         
         //considering we already have upto mid, now search from mid to str len
         for(int i = mid; i < len; i++){
            //curr window hash
            // a^26+s[ i ] so  discard the power[ ]^mid-1 , 

            //discard tail of window
            cur = ((cur - powerz[ mid - 1]*(s[ i-mid ]-'a'))%mod+mod)%mod;
            
            // extend head of window
            cur = (cur * 2 + (s[ i ]-'a'))%mod;

            // 0 1 2 3|4 5 6 7 slide the window from [1 . . . ]
            // if new rec it
            if(rollingHash.find(cur) == rollingHash.end() ){
                rollingHash[ cur ] = { i-mid + 1 }; // 3 | 4 [5] 5-3 + 1
            } else {
                // check if the substr overlaps, else new entry
                for(int ind : rollingHash[ cur ]){
                    string windowstr = s.substr( i-mid + 1, mid );
                    if( windowstr == s.substr( ind, mid  ) ){
                        //got a match
                        return windowstr;
                    }
            
                }
                  // new entry
                  rollingHash[ cur ].push_back({i-mid+1});
                }
            }
         //no overlap
         return string("");

     };

     //bs on mid , do rolling hash

     int low = 0, high = len;
     string ret = "";
     while(low <= high ){
        int mid = (low+high)/2;
        string str = rabinKarp(mid);
        if(str.size() > ret.size() ){
            ret = str;
            low = mid + 1;
        } else{
            high = mid - 1;
        }
     }
     return ret;
    }
};
382820