<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:
    template <typename T> vector<int> suffix_array(const T& S) {
        int n = S.size();
        vector<int> sa;
        for (int i = n - 1; i >= 0; --i)
            sa.push_back(i);
        stable_sort(sa.begin(), sa.end(),
                    [&](int a, int b) { return S[a] < S[b]; });
        vector<int> classes(n);
        for (int i = 0; i < n; ++i)
            classes[i] = S[i];
        for (int len = 1; len < n; len *= 2) {
            vector<int> c = classes;
            for (int i = 0; i < n; i++) {
                classes[sa[i]] =
                    i > 0 && c[sa[i - 1]] == c[sa[i]] && sa[i - 1] + len < n &&
                            c[sa[i - 1] + len / 2] == c[sa[i] + len / 2]
                        ? classes[sa[i - 1]]
                        : i;
            }
            vector<int> cnt(n);
            iota(cnt.begin(), cnt.end(), 0);
            vector<int> s = sa;
            for (int i = 0; i < n; i++) {
                int s1 = s[i] - len;
                if (s1 >= 0)
                    sa[cnt[classes[s1]]++] = s1;
            }
        }
        return sa;
    }
    template <typename T> vector<int> lcp_array(const T& s, vector<int>& rank) {
        int n = s.size(), k = 0;
        vector<int> sa = suffix_array(s);
        vector<int> lcp(n, 0);
        for (int i = 0; i < n; i++)
            rank[sa[i]] = i;
        for (int i = 0; i < n; i++, k ? k-- : 0) {
            if (rank[i] == n - 1) {
                k = 0;
                continue;
            }
            int j = sa[rank[i] + 1];
            while (i + k < n && j + k < n && s[i + k] == s[j + k])
                k++;
            lcp[rank[i]] = k;
        }
        return lcp;
    }
    string longestDupSubstring(string s) {
        int n = s.size();
        vector<int> rank(n);
        vector<int> lcp = lcp_array(s, rank), sfx = suffix_array(s);
        int mock = 0, len = -1;
        for (int i = 0; i <= n - 1; i++) {
            if (lcp[i] > len) {
                len = lcp[i];
                mock = sfx[i];
            }
        }
        string res = s.substr(mock, len);
        return res;
    }
};
83300