<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:
    def longestDupSubstring(self, s: str) -> str:
        # Method 1: Binary Search + Rabin-Karp Algorithm (with polynomial rolling hash). Time O(n * log n) Space O(n)
        n = len(s)
        kMod = 1_000_000_007

        pows = [0] * n
        pows[0] = 1
        for i in range(1, n):
            pows[i] = (pows[i - 1] * 26) % kMod

        best_start = -1

        left, right = 1, n
        while left < right:
            middle = ((right - left) >> 1) + left
            start = self.search(s, middle, pows, kMod)
            if start == -1:
                right = middle
            else:
                best_start = start
                left = middle + 1

        if best_start == -1:
            return ""
        
        if self.search(s, left, pows, kMod) == -1:
            return s[best_start:best_start + left - 1]
        
        return s[best_start:best_start + left]

    def search(self, s: str, k: int, pows: list[int], kMod: int) -> int:
        seen = {}
        hash_val = 0

        # Compute the hash value of s[:k].
        for i in range(k):
            hash_val = (hash_val * 26 + (ord(s[i]) - ord('a'))) % kMod
            
        if hash_val not in seen:
            seen[hash_val] = []
            
        seen[hash_val].append(0)

        # Compute the rolling hash by Rabin Karp.
        for i in range(k, len(s)):
            startIndex = i - k + 1
            hash_val = (hash_val - pows[k - 1] * (ord(s[i - k]) - ord('a')) % kMod + kMod) % kMod
            hash_val = (hash_val * 26 + (ord(s[i]) - ord('a'))) % kMod
            
            if hash_val in seen:
                currSub = s[startIndex:startIndex + k]
                for start in seen[hash_val]:
                    if s[start:start + k] == currSub:
                        return startIndex
                    
            if hash_val not in seen:
                seen[hash_val] = []
                
            seen[hash_val].append(startIndex)
            
        return -1

    def _longestDupSubstring(self, s: str) -> str:
        # Method 2: Suffix Array (Manber Myers Algorithm) + Longest Common Prefix (Kasai Algorithm). Time O(n * log n) Space O(n)
        n = len(s)
        suffix_array = self.manber_myers(s, list(range(n)), 1)
        lcp = self.kasai(s, suffix_array)
        if not any(l > 0 for l in lcp):
            return ""

        max_lcp = 0
        i = 0
        for j in range(len(lcp)):
            if lcp[j] > max_lcp:
                max_lcp = lcp[j]
                i = j

        return s[suffix_array[i]:suffix_array[i] + max_lcp]

    def manber_myers(self, s: str, buckets: List[int], order: int) -> List[int]:
        d = {}
        for bucket in buckets:
            key = s[bucket:bucket + order]
            if key not in d:
                d[key] = []
                
            d[key].append(bucket)

        suffix_array = []
        sorted_keys = sorted(d.keys())  # should be MSD Radix Sort
        for key in sorted_keys:
            v = d[key]
            if len(v) > 1:
                suffix_array.extend(self.manber_myers(s, v, order * 2))
            else:
                suffix_array.append(v[0])
                
        return suffix_array
    
    def kasai(self, s: str, suffix_array: List[int]) -> List[int]:
        n = len(suffix_array)
        rank = [0] * n
        for i in range(n):
            rank[suffix_array[i]] = i
        
        lcp = [0] * n
        k = 0
        for i in range(n):
            if rank[i] == n - 1:
                k = 0
                continue
                
            j = suffix_array[rank[i] + 1]
            while j + k < n and i + k < n and s[i + k] == s[j + k]:
                k += 1
                
            lcp[rank[i]] = k
            k = max(0, k - 1)
            
        return lcp

    def __longestDupSubstring(self, s: str) -> str:
        # Method 3: Suffix Tree (Ukkonen's Algorithm - build tree) + Longest Common Prefix. Time O(n) Space O(n)
        suffix_tree = SuffixTree(s)
        return "" if suffix_tree.lcp[0] == -1 else s[suffix_tree.lcp[0]:suffix_tree.lcp[1]]
    

class SuffixTreeNode:
    def __init__(self, start: int, end: List[int]) -> None:
        self.start = start
        self.end = end
        self.children = {}
        self.suffix_link = None

    def edge_length(self) -> int:
        return self.end[0] - self.start

class ActivePoint:
    def __init__(self, node: SuffixTreeNode, length: int) -> None:
        self.active_node = node
        self.active_length = length
        self.active_char_index = 0

    def walk_down(self, s: str) -> bool:
        child = self.active_node.children[s[self.active_char_index]]
        if self.active_length >= child.edge_length():
            self.active_char_index += child.edge_length()
            self.active_length -= child.edge_length()
            self.active_node = child
            return True

        return False

class SuffixTree:
    def __init__(self, s: str) -> None:
        self.s = s
        self.root = SuffixTreeNode(-1, [-1])
        self.active_point = ActivePoint(self.root, 0)
        self.remaining_number = 0
        self.prefix_count = 0
        self.leaf_end = [-1]
        self.lcp = [-1, -1]

        self.build()

    # Core Ukkonen's algorithm logic
    def build(self) -> None:
        self.s = self.s + '$' # Append sentinel character
        for i in range(len(self.s)):
            self.append_character(i)

    def append_character(self, i: int) -> None:
        last_new_node = None
        s_char = self.s[i]
        self.leaf_end[0] = i + 1
        self.remaining_number += 1

        while self.remaining_number > 0: # Canonicalization
            if self.active_point.active_length == 0:
                self.active_point.active_char_index = i

            active_char = self.s[self.active_point.active_char_index]
            if active_char in self.active_point.active_node.children:
                if self.active_point.walk_down(self.s):
                    continue

                next = self.active_point.active_node.children[active_char]
                next_cur_index = next.start + self.active_point.active_length
                next_char = self.s[next_cur_index]

                # Rule 3: Split edge
                if next_char == s_char:
                    self.active_point.active_length += 1
                    self.prefix_count += 1
                    if self.lcp[0] == -1 or self.lcp[1] - self.lcp[0] < self.prefix_count:
                        self.lcp[0] = next_cur_index + 1 - self.prefix_count
                        self.lcp[1] = next_cur_index + 1

                    if last_new_node is not None:
                        last_new_node.suffix_link = self.active_point.active_node

                    break

                # Rule 2: Advance cursor (internal node)
                internal = SuffixTreeNode(next.start, [next_cur_index]) # create the internal node
                self.active_point.active_node.children[active_char] = internal
                if self.lcp[0] == -1 or self.lcp[1] - self.lcp[0] < self.prefix_count:
                    self.lcp[0] = internal.end[0] - self.prefix_count
                    self.lcp[1] = internal.end[0]

                # update the next node and put as the internal node children
                next.start = next_cur_index
                internal.children[next_char] = next

                # Rule 1: Create a new leaf
                leaf = SuffixTreeNode(i, self.leaf_end) # create the leaf node
                internal.children[s_char] = leaf

                if last_new_node is not None:
                    last_new_node.suffix_link = internal # set the suffix link

                last_new_node = internal
            else:
                # Rule 1: Create a new leaf
                leaf = SuffixTreeNode(i, self.leaf_end)
                self.active_point.active_node.children[active_char] = leaf
                if last_new_node is not None:
                    last_new_node.suffix_link = self.active_point.active_node # set the suffix link
                    last_new_node = None

            self.remaining_number -= 1
            # Update the activePoint
            if self.active_point.active_node == self.root and self.active_point.active_length > 0:
                self.active_point.active_char_index = i - self.remaining_number + 1
                self.active_point.active_length -= 1
            elif self.active_point.active_node != self.root:
                self.active_point.active_node = self.active_point.active_node.suffix_link

            if self.prefix_count > 0:
                self.prefix_count -= 1


25300