<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 n = s.size();

        string res = "";
        unordered_set<char> ust;
        bool l1 = false;
        for (char& c : s) {
            if (ust.find(c) != ust.end()) {
                l1 = true;
                res += c;
                break;
            }
            ust.insert(c);
        }
        if (l1 == false) return "";

        gen_str_hash(s);

        int l = 1, r = n;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (l == mid) break;
            string tmp = check(s, mid);
            if (tmp.size() == 0) {
                r = mid;
            } else {
                l = mid;
                res = tmp;
            }
        }

        // // banana
        // cout << endl << endl;
        // hash_func(1, 4);
        // cout << endl;
        // hash_func(3, 6);
        return res;
    }

    vector<unsigned long> p;
    vector<unsigned long> hash;

    void gen_str_hash(string& s) {
        unsigned long prime = 37;
        int n = s.size();
        p.resize(n + 10);
        hash.resize(n + 10);
        hash[0] = s[0] - 'a';
        p[0] = 1;
        for (int i=1; i < n; ++i) {
            unsigned long cur = s[i] - 'a';
            hash[i] = hash[i-1] * prime + cur;
            p[i] = prime * p[i-1];
        }
        // std::copy(p.begin(), p.end(), std::ostream_iterator<unsigned long>(cout, ", "));
        // cout << endl;
        // std::copy(hash.begin(), hash.end(), std::ostream_iterator<unsigned long>(cout, ", "));
        // cout << endl;
    }

    unsigned long hash_func(int st, int ed) {
        // cout << "hash[ed-1]: " << hash[ed-1] << endl;
        // cout << "hash[st-1]: " << hash[st-1] << endl;
        // cout << "p[ed-st]: " << p[ed-st] << endl;
        if (st == 0) {
            return hash[ed-1];
        }
        return hash[ed-1] - hash[st-1] * p[ed-st];
    }


    string check(string& s, int len) {
        unordered_set<unsigned long> ust;
        int n = s.size();
        for (int i{0}; i <= n - len; ++i) {
            unsigned long h = hash_func(i, i + len);
            // cout << "substr is: " << s.substr(i, len) << endl
            //     << "hash is: " << h << endl;
            if (ust.find(h) != ust.end()) {
                return s.substr(i, len);
            }
            ust.insert(h);
        }
        return "";
    }
};

221540