最长重复子串（后缀数组解法）

题目描述
给定一个字符串s，找到其中最长的重复子串。重复子串是指在字符串中至少出现两次的连续子串（两次出现的位置可以重叠，但通常认为不重叠更有意义，这里我们考虑可以重叠的情况）。

解题过程

让我用循序渐进的方式为你讲解这个问题的后缀数组解法：

1. 问题分析

• 我们需要找到在字符串中出现至少两次的最长子串
• 暴力解法是枚举所有子串，检查每个子串出现的次数，时间复杂度O(n³)
• 使用后缀数组可以将时间复杂度优化到O(n log n)

2. 后缀数组基本概念

后缀数组包含字符串的所有后缀的起始位置，按字典序排序：

字符串s = "banana"
所有后缀：
0: "banana"
1: "anana" 
2: "nana"
3: "ana"
4: "na"
5: "a"

排序后的后缀数组：
5: "a"
3: "ana"
1: "anana"
0: "banana"
4: "na"
2: "nana"

3. 关键观察

两个后缀的最长公共前缀(LCP)就是它们对应的重复子串。在排序后的后缀数组中，相邻后缀的LCP包含了我们需要的重复子串信息。

4. 构建后缀数组

使用倍增算法构建后缀数组：

def build_suffix_array(s):
    n = len(s)
    # 初始排名（单个字符）
    suffix = list(range(n))
    rank = [ord(ch) for ch in s]
    
    k = 1
    while k < n:
        # 按第一关键字和第二关键字排序
        suffix.sort(key=lambda i: (rank[i], rank[i + k] if i + k < n else -1))
        
        # 重新计算排名
        new_rank = [0] * n
        new_rank[suffix[0]] = 0
        for i in range(1, n):
            prev = suffix[i-1]
            curr = suffix[i]
            # 如果两个元素的第一第二关键字都相同，排名相同
            if rank[prev] == rank[curr] and (prev + k < n and curr + k < n and rank[prev + k] == rank[curr + k]):
                new_rank[curr] = new_rank[prev]
            else:
                new_rank[curr] = new_rank[prev] + 1
        rank = new_rank
        k *= 2
    
    return suffix

5. 计算LCP数组

LCP数组存储相邻后缀的最长公共前缀长度：

def build_lcp_array(s, suffix):
    n = len(s)
    lcp = [0] * n
    # 构建逆后缀数组，用于快速查找位置
    rank = [0] * n
    for i in range(n):
        rank[suffix[i]] = i
    
    k = 0
    for i in range(n):
        if rank[i] == n - 1:
            k = 0
            continue
        
        j = suffix[rank[i] + 1]
        while i + k < n and j + k < n and s[i + k] == s[j + k]:
            k += 1
        
        lcp[rank[i]] = k
        if k > 0:
            k -= 1
    
    return lcp

6. 寻找最长重复子串

在LCP数组中找到最大值，对应的就是最长重复子串：

def longest_repeated_substring(s):
    if not s:
        return ""
    
    suffix = build_suffix_array(s)
    lcp = build_lcp_array(s, suffix)
    
    # 找到LCP数组中的最大值
    max_len = 0
    max_index = 0
    for i in range(len(lcp)):
        if lcp[i] > max_len:
            max_len = lcp[i]
            max_index = i
    
    if max_len == 0:
        return ""
    
    # 从后缀数组中获取重复子串
    start_pos = suffix[max_index]
    return s[start_pos:start_pos + max_len]

7. 完整示例

以字符串"banana"为例：

• 后缀数组：[5, 3, 1, 0, 4, 2]（对应后缀："a", "ana", "anana", "banana", "na", "nana"）
• LCP数组：[0, 1, 3, 0, 0, 2]
• 最大LCP值是3，对应后缀"ana"和"anana"的最长公共前缀"ana"
• 最长重复子串："ana"

8. 时间复杂度分析

• 构建后缀数组：O(n log n)
• 构建LCP数组：O(n)
• 总体时间复杂度：O(n log n)
• 空间复杂度：O(n)

这种方法相比暴力解法的O(n³)有了显著的性能提升，特别适合处理长字符串。