<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 {
    const int b = 256;
    const int p = 4001;
public:
    inline int powb(int L) {
        int h = 1;
        for (int i=1; i<L; i++) {
            h = (h * b) % p;
        }
        return h;
    }

    inline int newHash(int hash, string& s, int i, int L, int powB) {
        hash = (b * (hash - s[i - L] * powB) + s[i]) % p;
        if (hash < 0) hash += p;
        return hash;
    }

    bool match(string& s, int i, int j, int L) {
        //cout << "Matching " << i << "," << j << " " << L << "\n";
        for (int k=0; k<L; k++) {
            if (s[i+k] != s[j+k]) {
                return false;
            }
        }
        return true;
    }

    string isPresent(string& s, int K) {
        int hash = 0;
        int powB = powb(K);
        unordered_map<int, vector<int>> m;
        for (int i=0; i<K; i++) {
            hash = (hash * b + s[i]) % p;
        }
        m[hash].push_back(0);
        for (int i=K; i<s.size(); i++) {
            hash = newHash(hash, s, i, K, powB);
            if (m.find(hash) != m.end()) {
                for (int p : m[hash]) {
                    if (match(s, p, i-K+1, K)) {
                        return s.substr(p, K);
                    }
                }
            }
            m[hash].push_back(i-K+1);
        }
        return "";
    }

    string longestDupSubstring(string s) {
        int n = s.size();
        int i = 1;
        int m = 0;
        string res = "";
        while (i <= n) {
            m = i + (n - i)/ 2;
            //cout << m << "," << i << "," << n << "\n";
            string t = isPresent(s, m);
            if (!t.empty()) {
                if (t.size() > res.size()) {
                    res = t;
                }
                i = m + 1;
            } else {
                n = m - 1;
            }
        }
        cout << "Res " << res;
        return res;
    }
};
175460