<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();
	    int k;
        vector<int> sa(n+1);
        vector<int> tmp(n+1);
        vector<int> rank(n+1);
	    vector<int> lcp(n+1);
        for(int i = 0; i <= n; ++i) {
            sa[i] = i;
            rank[i] = i < n ? s[i] : -1;
        }
        auto cmp = [&rank, &k, n] (int i, int j) {
            if (rank[i] != rank[j]) {
                return rank[i] < rank[j];
            } else {
                int ri = i + k <= n ? rank[i+k] : -1;
                int rj = j + k <= n ? rank[j+k] : -1;
                return ri < rj;
            }
        };
        for (k = 1; k <= n; k *= 2) {
            sort(sa.begin(), sa.end(), cmp);
            tmp[sa[0]] = 0;
            for(int i = 1; i <= n; ++i) {
                tmp[sa[i]] = tmp[sa[i-1]] + (cmp(sa[i-1], sa[i]) ? 1 : 0);
            }
            for (int i = 0; i <= n; i++) {
                rank[i] = tmp[i];
            }
        }

        lcp[0] = 0;
        int h = 0;
        for (int i = 0; i <= n; i++) rank[sa[i]] = i;
        for (int i = 0; i < n; i++) {
            int j = sa[rank[i] - 1];
            if (h > 0) h--;
            for (; j + h < n && i + h < n; h++) {
            if (s[j + h] != s[i + h]) break;
            }
            lcp[rank[i]-1] = h;
        }
        
        int ans=0;
        int m = 0;
        for (int i = 0; i <= n; i++) {
            if (lcp[i] > m) {
            m = lcp[i];
            ans = sa[i];
            }
        }
        
        return s.substr(ans, m);
    }
};
19940