<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 {
    int MAX;
    vector<int> buildSA(string& s) {
        int n = s.size();
        vector<int> sa(n+1), rank(n+1);
        sa[n] = n;
        for (int i = 0; i < n; ++i) {
            sa[i] = i;
            rank[i] = s[i];
        }
        int gap = 1;
        while (rank[sa[n]] != n) {
            vector<int> freq(MAX);
            for (int i = 0; i <= n; ++i) {
                int curr = rank[min(i+gap, n)];
                ++freq[curr];
            }
            for (int i = 0; i < MAX-1; ++i) freq[i+1] += freq[i];
            vector<int> pos(n+1);
            for (int i = n; i >= 0; --i) {
                int curr = rank[min(i+gap, n)];
                --freq[curr];
                pos[freq[curr]] = i;
            }
            
            freq = vector<int>(MAX);
            for (int i = 0; i <= n; ++i) ++freq[rank[i]];
            for (int i = 0; i < MAX-1; ++i) freq[i+1] += freq[i];
            for (int i = n; i >= 0; --i) {
                int curr = rank[pos[i]];
                --freq[curr];
                sa[freq[curr]] = pos[i];
            }
            
            auto compare = [&rank, &gap, &n](auto i, auto j) {
                if (rank[i] != rank[j]) return rank[i] < rank[j];
                i = i+gap; j = j+gap;
                if (i <= n && j <= n) return rank[i] < rank[j];
                return j < i;
            };
            vector<int> nrank(n+1);
            for (int i = 0; i < n; ++i) {
                nrank[sa[i+1]] = nrank[sa[i]] + compare(sa[i], sa[i+1]);
            }
            rank = nrank;
            gap <<= 1;
        }
        return sa;
    }
    
    vector<int> buildLCPA(string& s, vector<int>& sa) {
        int n = s.size();
        vector<int> lcpa(n+1);
        vector<int> pos(n+1);
        for (int i = 0; i <= n; ++i) pos[sa[i]] = i;
        int k = 0;
        for (int i = 0; i <= n; ++i) {
            if (pos[i] == n) continue;
            int j = sa[pos[i]+1];
            while (i+k < n && j+k < n && s[i+k] == s[j+k]) ++k;
            lcpa[pos[i]+1] = k;
            if (k) --k;
        }
        return lcpa;
    }
public:
    string longestDupSubstring(string s) {
        MAX = max((int)s.size()+1, 256);
        vector<int> sa = buildSA(s);
        vector<int> lcpa = buildLCPA(s, sa);
        int max_len = 0, start = 0;
        for (int i = 2; i <= s.size(); ++i) {
            if (max_len < lcpa[i]) {
                start = sa[i];
                max_len = lcpa[i];
            }
        }
        return s.substr(start, max_len);
    }
};
42980