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

题目描述
给定一个字符串s，找到最长的重复子串的长度。"重复"意味着在字符串中至少出现两次（可以重叠）的连续子串。要求时间复杂度优于O(n²)。

解题过程

1. 问题分析

• 暴力解法需要枚举所有子串O(n²)并检查出现次数O(n)，总复杂度O(n³)
• 我们需要利用后缀数组和高度数组来优化

2. 后缀数组基础概念

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

示例：s = "banana"

• 后缀：
  0: "banana"
  1: "anana"
  2: "nana"
  3: "ana"
  4: "na"
  5: "a"

• 排序后的后缀数组SA：[5, 3, 1, 0, 4, 2]
  (对应后缀："a", "ana", "anana", "banana", "na", "nana")

3. 高度数组概念

高度数组LCP[i]表示排序后相邻两个后缀的最长公共前缀长度。

对于SA = [5,3,1,0,4,2]：

• LCP[1]：比较"a"和"ana" → 公共前缀"a" → 长度1
• LCP[2]：比较"ana"和"anana" → 公共前缀"ana" → 长度3
• LCP[3]：比较"anana"和"banana" → 公共前缀"" → 长度0
• LCP[4]：比较"banana"和"na" → 公共前缀"" → 长度0
• LCP[5]：比较"na"和"nana" → 公共前缀"na" → 长度2

4. 关键观察

最长重复子串的长度就是高度数组中的最大值！

为什么？

• 排序后相邻后缀的公共前缀就是重复出现的子串
• 高度数组记录了这些公共前缀的长度
• 最大值就是最长的重复子串

5. 构建后缀数组

使用倍增算法，时间复杂度O(n log n)：

def build_suffix_array(s):
    n = len(s)
    # 初始排序：按第一个字符排序
    sa = list(range(n))
    rank = [ord(ch) for ch in s]
    
    k = 1
    while k < n:
        # 按(rank[i], rank[i+k])双关键字排序
        sa.sort(key=lambda i: (rank[i], rank[i + k] if i + k < n else -1))
        
        # 重新计算rank
        new_rank = [0] * n
        new_rank[sa[0]] = 0
        for i in range(1, n):
            prev = (rank[sa[i-1]], rank[sa[i-1] + k] if sa[i-1] + k < n else -1)
            curr = (rank[sa[i]], rank[sa[i] + k] if sa[i] + k < n else -1)
            new_rank[sa[i]] = new_rank[sa[i-1]] + (1 if prev != curr else 0)
        
        rank = new_rank
        if rank[sa[n-1]] == n-1:
            break
        k *= 2
    
    return sa

6. 构建高度数组

def build_lcp(s, sa):
    n = len(s)
    lcp = [0] * n
    rank = [0] * n
    
    # 构建rank数组：rank[i]表示后缀i在sa中的位置
    for i in range(n):
        rank[sa[i]] = i
    
    k = 0
    for i in range(n):
        if rank[i] == n-1:
            k = 0
            continue
        
        j = sa[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

7. 完整算法

def longest_repeating_substring(s):
    if not s:
        return 0
    
    sa = build_suffix_array(s)
    lcp = build_lcp(s, sa)
    
    return max(lcp) if lcp else 0

# 示例
s = "banana"
result = longest_repeating_substring(s)  # 返回3，对应"ana"

8. 算法分析

• 时间复杂度：O(n log n)，主要来自后缀数组构建
• 空间复杂度：O(n)，用于存储后缀数组和高度数组
• 相比暴力解法的O(n³)有显著优化

9. 特殊情况处理

• 空字符串：返回0
• 无重复子串：返回0
• 全相同字符：返回n-1

这种方法高效地找到了最长重复子串，是处理字符串重复模式识别的经典算法。