<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:
    int base = 31;
    int mod = 1e9 + 7;
    vector<long long> hash;
    vector<long long> powerlist;

    void computePrefixHashes(string& s) {
        int n = s.size();
        hash.resize(n + 1, 0);
        powerlist.resize(n + 1, 1);
        long long currentHash = 0;
        for (int i = 0; i < n; ++i) {
            currentHash = (currentHash * base + s[i]) % mod;
            hash[i + 1] = currentHash;
            powerlist[i + 1] = (powerlist[i] * base) % mod;
        }
    }

    long long getSubHash(int l, int r) {
        long long power = powerlist[r - l + 1];
        long long hashValue = (hash[r + 1] - (hash[l] * power) % mod + mod) % mod;
        return hashValue;
    }

    string longestDupSubstring(string s) {
        int len = 0;
        int index = -1;
        int low = 1;
        int high = s.size() - 1;
        int n = s.size();
        computePrefixHashes(s);
        
        while (low <= high) {
            int mid = (low + high) / 2;
            unordered_map<long long, vector<int>> mp;
            bool possible = false;
            for (int i = 0; i < n - mid + 1; i++) {
                long long w = getSubHash(i, i + mid - 1);
                if (mp.count(w)) {
                    for (int start : mp[w]) {
                        if (s.substr(start, mid) == s.substr(i, mid)) {
                            possible = true;
                            len = mid;
                            index = i;
                            break;
                        }
                    }
                }
                if (possible) break;
                mp[w].push_back(i);
            }
            if (possible) low = mid + 1;
            else high = mid - 1;
        }
        
        return index != -1 ? s.substr(index, len) : "";
    }
};

434660