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

constexpr int MAXN = 1<<17;
string S;
int N, gap;
int sa[MAXN], pos[MAXN], tmp[MAXN], lcp[MAXN];
bool sufCmp(int i, int j) {
    if (pos[i] != pos[j]) return pos[i] < pos[j];
    i += gap; j += gap;
    return (i < N && j < N) ? pos[i] < pos[j] : i > j;
}
void buildSA() {
    N = S.length();
    for (int i = 0; i < N; ++i) sa[i] = i, pos[i] = S[i];
    for (gap = 1;; gap *= 2) {
        sort(sa, sa+N, sufCmp);
        for (int i = 0; i < N-1; ++i) tmp[i+1] = tmp[i] + sufCmp(sa[i], sa[i+1]);
        for (int i = 0; i < N; ++i) pos[sa[i]] = tmp[i];
        if (tmp[N-1] == N-1) break;
    }
}
void buildLCP() {
    for (int i = 0, k = 0; i < N; ++i) {
        if (pos[i] == N-1) continue;
        for (int j = sa[pos[i]+1]; S[i+k] == S[j+k];) ++k;
        lcp[pos[i]] = k;
        if (k) --k;
    }
}
class Solution {
public:
    string longestDupSubstring(string s) {
        S = s;
        buildSA();
        buildLCP();
        int maxLen = 0, start = 0;
        for (int i = 0; i < N-1; ++i) {
            if (maxLen < lcp[i]) {
                maxLen = lcp[i];
                start = sa[i];
            }
        }
        return S.substr(start, maxLen);
    }
};
14180