<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>

#define ull unsigned long long

const int N = 300007;
vector<ull> powers1(N);
vector<ull> powers2(N);

class RollingHash {
public:
    RollingHash() : p1(31), p2(41), mod(4000000007) {}


    ull to_int(char c) {
        return (c - 'a' + 1);
    }


    pair<ull, ull> hash(const std::string& s, int n) {
        ull hash1 = 0, hash2 = 0;

        for (int i = n - 1; i >= 0; i--) {
            hash1 = (hash1 + to_int(s[i]) * powers1[n - i - 1]) % mod;
            hash2 = (hash2 + to_int(s[i]) * powers2[n - i - 1]) % mod;
        }

        return {hash1, hash2};
    }


    ull skip(ull hash, ull power, char c) {
        hash = (hash + mod - (to_int(c) * power) % mod) % mod;
        return hash;
    }

    ull append(ull hash, ull power, char c) {
        hash = ((hash * power) % mod + to_int(c)) % mod;
        return hash;
    }

private:
    ull p1, p2, mod;
};


class Solution {
public:
    bool can(const std::string& s, int length) {
        std::unordered_set<ull> seen1;
        std::unordered_set<ull> seen2;
        RollingHash rolling_hash;

        if (length == 0) return true;

        auto hash = rolling_hash.hash(s, length);
        ull hash1 = hash.first;
        ull hash2 = hash.second;
        seen1.insert(hash1);
        seen2.insert(hash2);

        for (int i = length; i < s.size(); i++) {
            hash1 = rolling_hash.append(hash1, powers1[1], s[i]);
            hash1 = rolling_hash.skip(hash1, powers1[length], s[i - length]);

            hash2 = rolling_hash.append(hash2, powers2[1], s[i]);
            hash2 = rolling_hash.skip(hash2, powers2[length], s[i - length]);

            if (seen1.find(hash1) != seen1.end() && seen2.find(hash2) != seen2.end()) {
                result = s.substr(i - length + 1, length);
                return true;
            }

            seen1.insert(hash1);
            seen2.insert(hash2);
        }

        return false;
    }

    std::string longestDupSubstring(const std::string& s) {
        int left = 1, right = s.size() - 1;
        ull p1 = 31,  p2 = 41, mod = 4e9 + 7;

        ull power1 = 1, power2 = 1;
        for (int i = 0; i < N; i++) {
            powers1[i] = power1;
            power1 = (power1 * p1) % mod;

            powers2[i] = power2;
            power2 = (power2 * p2) % mod;
        }

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (can(s, mid)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return result;
    }

private:
    std::string result = "";
};

411620