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

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <string>

using namespace std; // std::

struct SuffixTreeNode {
    int start, *end;
    unordered_map<char, SuffixTreeNode*> children;
    SuffixTreeNode* suffixLink;

    SuffixTreeNode(int start, int* end) : start(start), end(end), suffixLink(nullptr) {}

    int edgeLength() {
        return *end - start;
    }
};

struct ActivePoint {
    SuffixTreeNode* activeNode;
    int activeLength;
    int activeCharIndex;

    ActivePoint(SuffixTreeNode* node, int length) : activeNode(node), activeLength(length), activeCharIndex(0) {}

    bool walkDown(const string &s) {
        SuffixTreeNode* child = activeNode->children[s[activeCharIndex]];
        if (activeLength >= child->edgeLength()) {
            activeCharIndex += child->edgeLength();
            activeLength -= child->edgeLength();
            activeNode = child;
            return true;
        }
        return false;
    }
};

class SuffixTree {
public:
    string s;
    SuffixTreeNode* root;
    ActivePoint activePoint;
    int remainingNumber;
    int prefixCount;
    int leafEnd;
    pair<int, int> lcp;

    SuffixTree(const string &s) : s(s + "$"), root(new SuffixTreeNode(-1, new int(-1))), activePoint(root, 0), remainingNumber(0), prefixCount(0), leafEnd(-1), lcp(-1, -1) {
        build();
    }

    void build() {
        for (int i = 0; i < s.length(); ++i) {
            appendCharacter(i);
        }
    }

    void appendCharacter(int i) {
        SuffixTreeNode* lastNewNode = nullptr;
        char sChar = s[i];
        leafEnd = i + 1;
        remainingNumber++;

        while (remainingNumber > 0) { // Canonicalization
            if (activePoint.activeLength == 0) {
                activePoint.activeCharIndex = i;
            }
            char activeChar = s[activePoint.activeCharIndex];
            if (activePoint.activeNode->children.count(activeChar)) {
                if (activePoint.walkDown(s)) {
                    continue;
                }

                SuffixTreeNode* next = activePoint.activeNode->children[activeChar];
                int nextCurIndex = next->start + activePoint.activeLength;
                char nextChar = s[nextCurIndex];

                // Rule 3: Split edge
                if (nextChar == sChar) {
                    activePoint.activeLength++;
                    prefixCount++;
                    if (lcp.first == -1 || lcp.second - lcp.first < prefixCount) {
                        lcp.first = nextCurIndex + 1 - prefixCount;
                        lcp.second = nextCurIndex + 1;
                    }
                    if (lastNewNode) {
                        lastNewNode->suffixLink = activePoint.activeNode;
                    }
                    break;
                }
                // Rule 2: Advance cursor (internal node)
                SuffixTreeNode* internal = new SuffixTreeNode(next->start, new int(nextCurIndex)); // create the internal node
                activePoint.activeNode->children[activeChar] = internal;
                if (lcp.first == -1 || lcp.second - lcp.first < prefixCount) {
                    lcp.first = *internal->end - prefixCount;
                    lcp.second = *internal->end;
                }

                // update the next node and put as the internal node children
                next->start = nextCurIndex;
                internal->children[s[nextCurIndex]] = next;

                // Rule 1: Create a new leaf
                SuffixTreeNode* leaf = new SuffixTreeNode(i, &leafEnd); // create the leaf node
                internal->children[sChar] = leaf;

                if (lastNewNode) {
                    lastNewNode->suffixLink = internal; // set the suffix link
                }
                lastNewNode = internal;
            } else {
                // Rule 1: Create a new leaf
                SuffixTreeNode* leaf = new SuffixTreeNode(i, &leafEnd);
                activePoint.activeNode->children[activeChar] = leaf;
                if (lastNewNode) {
                    lastNewNode->suffixLink = activePoint.activeNode; // set the suffix link
                    lastNewNode = nullptr;
                }
            }

            remainingNumber--;
            // Update the activePoint
            if (activePoint.activeNode == root && activePoint.activeLength > 0) {
                activePoint.activeCharIndex = i - remainingNumber + 1;
                activePoint.activeLength--;
            } else if (activePoint.activeNode != root) {
                activePoint.activeNode = activePoint.activeNode->suffixLink;
            }

            if (prefixCount > 0) {
                prefixCount--;
            }
        }
    }
};

class Solution {
public:
    static string _longestDupSubstring(const string s) {
        // Method 1: Binary Search + Rabin-Karp Algorithm (with polynomial rolling hash). Time O(n * log n) Space O(n)
        const int n = s.length();
        const int kMod = 1'000'000'007;

        vector<long long> pows(n, 1);
        for (int i = 1; i < n; ++i) {
            pows[i] = pows[i - 1] * 26 % kMod;
        }

        int bestStart = -1;
        int left = 1, right = n;
        while (left < right) {
            const int middle = ((right - left) >> 1) + left;
            int start = search(s, middle, pows, kMod);
            if (start == -1) {
                right = middle;
            } else {
                bestStart = start;
                left = middle + 1;
            }
        }

        if (bestStart == -1) {
            return "";
        }
        if (search(s, left, pows, kMod) == -1) {
            return s.substr(bestStart, left - 1);
        }
        return s.substr(bestStart, left);
    }

private:
    static int search(const string &s, const int k, const vector<long long> &pows, const int kMod) {
        unordered_map<long long, vector<int>> seen;
        long long hash = 0;

        for (int i = 0; i < k; ++i) {
            hash = (hash * 26 + (s[i] - 'a')) % kMod;
        }
        seen[hash].push_back(0);

        for (int i = k; i < s.length(); ++i) {
            int startIndex = i - k + 1;
            hash = (hash - pows[k - 1] * (s[i - k] - 'a') % kMod + kMod) % kMod;
            hash = (hash * 26 + (s[i] - 'a')) % kMod;

            if (seen.find(hash) != seen.end()) {
                string currSub = s.substr(startIndex, k);
                for (int start : seen[hash]) {
                    if (s.substr(start, k) == currSub) {
                        return startIndex;
                    }
                }
            }
            seen[hash].push_back(startIndex);
        }
        return -1;
    }

public:
    static string __longestDupSubstring(const string s) {
        // Method 2: Suffix Array (Manber Myers Algorithm) + Longest Common Prefix (Kasai Algorithm). Time O(n * log n) Space O(n)
        const int n = s.length();
        vector<int> suffixArray = manberMyers(s);
        vector<int> lcp = kasai(s, suffixArray);
        if (none_of(lcp.begin(), lcp.end(), [](int l) { return l > 0; })) {
            return "";
        }

        int maxLcp = 0, i = 0;
        for (int j = 0; j < lcp.size(); ++j) {
            if (lcp[j] > maxLcp) {
                maxLcp = lcp[j];
                i = j;
            }
        }
        return s.substr(suffixArray[i], maxLcp);
    }

private:
    static vector<int> manberMyers(const string &s) {
        const int n = s.length();
        vector<int> suffixArray(n);
        vector<int> order(n);
        vector<int> nextOrder(n);

        for (int i = 0; i < n; i++) {
            suffixArray[i] = i;
            order[i] = s[i];
        }

        for (int len = 1; len < n; len *= 2) {
            const auto compare = [&order, &n, &len](const int a, const int b) {
                if (order[a] != order[b]) {
                    return order[a] < order[b];
                }
                int aNext = (a + len < n) ? order[a + len] : -1;
                int bNext = (b + len < n) ? order[b + len] : -1;
                return aNext < bNext;
            };
            sort(suffixArray.begin(), suffixArray.end(), compare);

            nextOrder[suffixArray[0]] = 0;
            for (int i = 1; i < n; i++) {
                if (order[suffixArray[i]] == order[suffixArray[i - 1]]) {
                    const int cur = suffixArray[i];
                    const int prev = suffixArray[i - 1];
                    if (cur + len < n && prev + len < n && order[cur + len] == order[prev + len]) {
                        nextOrder[cur] = nextOrder[prev];
                    } else {
                        nextOrder[cur] = nextOrder[prev] + 1;
                    }
                } else {
                    nextOrder[suffixArray[i]] = nextOrder[suffixArray[i - 1]] + 1;
                }
            }
            order = nextOrder;
        }

        return suffixArray;
    }

private:
    static vector<int> kasai(const string &s, const vector<int> &suffixArray) {
        const int n = suffixArray.size();
        vector<int> rank(n);
        for (int i = 0; i < n; ++i) {
            rank[suffixArray[i]] = i;
        }

        vector<int> lcp(n, 0);
        for (int i = 0, k = 0; i < n; ++i) {
            if (rank[i] == n - 1) {
                k = 0;
                continue;
            }
            const int j = suffixArray[rank[i] + 1];
            while (j + k < n && i + k < n && s[i + k] == s[j + k]) {
                ++k;
            }
            lcp[rank[i]] = k;
            if (k > 0) {
                --k;
            }
        }
        return lcp;
    }

public:
    static string longestDupSubstring(const string s) {
        // Method 3: Suffix Tree (Ukkonen's Algorithm - build tree) + Longest Common Prefix. Time O(n) Space O(n)
        SuffixTree suffixTree(s);
        return suffixTree.lcp.first == -1 ? "" : s.substr(suffixTree.lcp.first, suffixTree.lcp.second - suffixTree.lcp.first);
    }
};

66020