<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) {
        string res;
        int n = s.size(), left = 0, right = n, M = 1e7 + 7;
        vector<int> power(n);
        for (int i = 0; i < n; ++i) {
            power[i] = (i == 0) ? 1 : (power[i - 1] * 26) % M;
        }
        while (left < right) {
            int mid = left + (right - left) / 2;
            string dup = rabinKarp(s, mid, power);
            if (dup.size() > res.size()) {
                res = dup;
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return res;
    }
    string rabinKarp(string s, int len, vector<int>& power) {
        if (len == 0) return "";
        int n = s.size(), cur = 0, M = 1e7 + 7;
        unordered_map<int, vector<int>> hash;
        for (int i = 0; i < len; ++i) {
            cur = (cur * 26 + (s[i] - 'a')) % M;
        }
        hash[cur] = {0};
        for (int i = len; i < n; ++i) {
            cur = ((cur - power[len - 1] * (s[i - len] - 'a')) % M + M) % M;
            cur = (cur * 26 + (s[i] - 'a')) % M;
            if (!hash.count(cur)) {
                hash[cur] = {i - len + 1};
            } else {
                for (int idx : hash[cur]) {
                    if (s.substr(idx, len) == s.substr(i - len + 1, len)) return s.substr(idx, len);
                }
                hash[cur].push_back(i - len + 1);
            }
        }
        return "";
    }
};
// class Solution {
//     typedef uint64_t LL;
// public:
//     string longestDupSubstring(string s) {
//         if (s.empty()) return "";

//         const int n = (int)s.length();
//         unordered_map<int, int> len2StartIdx = {};
//         int start = 0;
//         int end = n-1;
        
//         while (start + 1 < end) {
//             const int mid = start + (end-start)/2;
//             if (this->check(s, mid, len2StartIdx)) {
//                 start = mid; 
//             } else {
//                 end = mid;
//             }
//         }

//         if (this->check(s, end, len2StartIdx))
//             return s.substr(len2StartIdx[end], end);
//         if (this->check(s, start, len2StartIdx))
//             return s.substr(len2StartIdx[start], start);
//         return "";
//     }
// private:
//     bool check(string& s, const int len, unordered_map<int, int>& len2StartIdx) {
//         const int n = (int)s.length();
//         const LL base = 31;
//         // const LL mod = (1l<<32);
//         unordered_set<LL> hashCodeSet;
//         LL hash = 0;
//         LL highestBase = 1; // highest number 1000..000 (in base 31)

//         for (int i = 0; i < len; ++i)
//             // highestBase = (highestBase * base) % mod;
//             highestBase = (highestBase * base);                    
        
//         // maintain a fixed length sliding window for substring
//         for (int i = 0; i < n; ++i) {
//             // convert the string to a base 26 number
//             // e.g. "bcd" ==>> ((1 * 31) + 2) * 31 + 3
//             hash = (hash*base + (s[i]-'a'));

//             if (i >= len) // remove the highest digit number
//                 hash = (hash - highestBase*(s[i-len]-'a') );                           

//             if (i >= len-1) {
//                 if (hashCodeSet.count(hash)) {
//                     len2StartIdx[len] = i-len+1;
//                     return true;
//                 }
//                 hashCodeSet.insert(hash);
//             }
//         }

//         return false;
//     }
// };
451940