第 79 课：后缀数组

难度： Advanced
所属模块： 高级数据结构
标签： suffix-array, lcp, string, sorting

1. 学习目标

通过本课的学习，你将能够：

理解后缀数组（Suffix Array, SA）的定义及其在解决字符串问题中的核心作用。
实现一种时间复杂度为 O(n log n) 的后缀数组构建算法（倍增算法）。
计算最长公共前缀（Longest Common Prefix, LCP）数组，并理解其与后缀数组的关系。
应用后缀数组与LCP数组解决经典字符串问题，如最长重复子串。

2. 核心概念

什么是后缀数组？

想象一下，你有一个字符串，比如 "banana"。后缀就是这个字符串从任意位置开始到末尾的子串。 "banana" 的所有后缀是：

位置0: banana
位置1: anana
位置2: nana
位置3: ana
位置4: na
位置5: a

现在，将这些后缀按照字典序（就像查字典一样排序）排列，我们得到一个有序列表：

a (位置5)
ana (位置3)
anana (位置1)
banana (位置0)
na (位置4)
nana (位置2)

后缀数组（SA） 就是这个有序列表中，每个后缀在原始字符串中的起始位置组成的数组。对于 "banana"，其后缀数组 SA = [5, 3, 1, 0, 4, 2]。

为什么需要它？ 后缀数组将字符串的复杂结构组织成有序形式，使得许多原本需要 O(n²) 甚至更高复杂度的字符串问题（如查找最长重复子串、模式匹配）可以在 O(n log n) 或更优的时间内解决。

最长公共前缀（LCP）数组

LCP数组是后缀数组的“伴侣”。LCP[i] 定义为：在排序后的后缀数组中，第 i 个后缀和第 i-1 个后缀 的最长公共前缀的长度。

对于上述 "banana" 的后缀排序列表：

LCP[1] (比较 a 和 ana) 公共前缀是 a，长度 = 1
LCP[2] (比较 ana 和 anana) 公共前缀是 an，长度 = 2
LCP[3] (比较 anana 和 banana) 公共前缀是空，长度 = 0
...

所以 LCP 数组（通常 LCP[0] 未定义或设为0）大致为 [0, 1, 2, 0, 1, 0]。

LCP数组的作用：它揭示了相邻后缀的相似程度。结合SA，我们可以高效地找到字符串中任意两个后缀的公共前缀长度，这是许多高级算法（如求最长重复子串）的基础。

构建算法简介

直接对所有后缀排序，如果使用快速排序，复杂度是 O(n log n) * O(n) = O(n² log n)，对于长字符串太慢。倍增算法是一种优雅的优化：

初始：只考虑每个后缀的第1个字符进行排序。
倍增：现在考虑前2个字符、前4个字符、前8个字符… 直到排序窗口覆盖整个字符串。
关键：在每一轮，我们利用上一轮的排序结果（排名）作为“关键字”，来对当前长度的子串进行排序。由于子串的前半部分和后半部分的排名我们已知，可以通过双关键字排序（基数排序）在 O(n) 时间内完成一轮。总共进行 O(log n) 轮，因此总复杂度为 O(n log n)。

3. 代码示例

以下是一个完整的 Python 实现，包括构建后缀数组（使用倍增算法）和计算LCP数组。

def build_suffix_array(s):
    """
    使用倍增算法构建后缀数组。
    :param s: 输入字符串
    :return: 后缀数组 SA，SA[i] 表示排序第 i 名的后缀的起始位置
    """
    n = len(s)
    # 初始化：按第一个字符排序
    sa = list(range(n))
    rank = [ord(c) for c in s]  # 初始排名就是字符的ASCII码
    k = 1
    
    while k < n:
        # 按 (rank[i], rank[i+k]) 双关键字排序
        # 为了方便，我们构建一个元组列表进行排序
        # 注意处理 i+k >= n 的情况，用 -1 作为哨兵（比任何排名都小）
        keys = [(rank[i], rank[i + k] if i + k < n else -1, i) for i in range(n)]
        keys.sort()
        
        # 根据排序结果更新 sa 和新的 rank
        new_sa = [item[2] for item in keys]
        new_rank = [0] * n
        # 为每个后缀分配新的排名（从0开始）
        r = 0
        new_rank[new_sa[0]] = 0
        for i in range(1, n):
            # 如果当前元组与前一个不同，排名加1
            if (keys[i][0] != keys[i-1][0]) or (keys[i][1] != keys[i-1][1]):
                r += 1
            new_rank[new_sa[i]] = r
        
        sa, rank = new_sa, new_rank
        k *= 2  # 窗口长度倍增
        
        # 优化：如果所有排名都已唯一，则提前结束
        if r == n - 1:
            break
            
    return sa

def build_lcp_array(s, sa):
    """
    使用Kasai算法在线性时间内构建LCP数组。
    :param s: 原始字符串
    :param sa: 后缀数组
    :return: LCP数组，LCP[i] 表示 sa[i] 和 sa[i-1] 对应后缀的最长公共前缀长度
    """
    n = len(s)
    # rank[i] 表示起始位置为 i 的后缀在 SA 中的排名（即 sa[rank[i]] == i）
    rank = [0] * n
    for i, pos in enumerate(sa):
        rank[pos] = i
    
    lcp = [0] * n
    h = 0  # 当前公共前缀长度
    
    # 按照后缀在原串中的位置顺序遍历 (i = 0, 1, ..., n-1)
    for i in range(n):
        if rank[i] > 0:  # 不是字典序最小的后缀
            j = sa[rank[i] - 1]  # 获取在SA中排在前一位的后缀的起始位置
            # 计算后缀 i 和后缀 j 的公共前缀长度
            while i + h < n and j + h < n and s[i + h] == s[j + h]:
                h += 1
            lcp[rank[i]] = h
            if h > 0:
                h -= 1  # 关键：下一个后缀至少有 h-1 的公共前缀
    return lcp

# --- 测试 ---
s = "banana"
sa = build_suffix_array(s)
lcp = build_lcp_array(s, sa)

print("原字符串:", s)
print("后缀数组 (SA):", sa)
print("SA对应的后缀顺序:")
for i, pos in enumerate(sa):
    print(f"  SA[{i}] = {pos}, 后缀: '{s[pos:]}'")
print("最长公共前缀数组 (LCP):", lcp)

运行结果示例：

原字符串: banana
后缀数组 (SA): [5, 3, 1, 0, 4, 2]
SA对应的后缀顺序:
  SA[0] = 5, 后缀: 'a'
  SA[1] = 3, 后缀: 'ana'
  SA[2] = 1, 后缀: 'anana'
  SA[3] = 0, 后缀: 'banana'
  SA[4] = 4, 后缀: 'na'
  SA[5] = 2, 后缀: 'nana'
最长公共前缀数组 (LCP): [0, 1, 2, 0, 1, 0]

注意：上述倍增算法的实现为了清晰易懂，使用了Python的元组排序。在实际竞赛或高性能场景中，通常会使用基于计数的基数排序（Radix Sort）来实现双关键字排序，以达到严格的 O(n log n) 或 O(n) 复杂度。

4. 实践练习

练习1：基础验证

给定字符串 s = "abracadabra"，手动或使用代码计算其后缀数组（SA）和最长公共前缀数组（LCP）的前5个元素。 要求： 写出你的推理过程或代码输出。 预期输出：

SA 前5个: [11, 10, 7, 0, 3] (对应后缀: 'a', 'ra', 'abra', 'abracadabra', 'acadabra')
LCP 前5个: [0, 0, 1, 1, 0] (LCP[0]未定义或为0，LCP[1]比较'a'和'ra'，LCP[2]比较'ra'和'abra'...)

练习2：应用LCP

在练习1的基础上，利用后缀数组和LCP数组，找出字符串 "abracadabra" 中最长的重复子串。 提示： 最长重复子串的长度等于LCP数组中的最大值。该最大值对应的相邻两个后缀（SA[i] 和 SA[i-1]）共享的前缀就是这个最长重复子串。 要求： 写出代码或推理过程，输出该最长重复子串及其长度。 预期输出：

最长重复子串: 'abra', 长度: 4

练习3：挑战 - 无重叠重复子串

在练习2的基础上，将问题升级：找出字符串 "abcabcabc" 中出现两次且互不重叠的最长子串。 要求： 编写一个函数，输入字符串，返回最长无重叠重复子串的长度和其中一个子串。 提示： 这需要结合后缀数组、LCP数组以及一些二分查找或滑动窗口的技巧。你可以考虑对可能的子串长度进行二分，然后检查在SA和LCP中是否存在长度>=该值且起始位置间隔足够大的相邻后缀对。

5. 常见错误

索引偏移（Off-by-one Error）：后缀数组和LCP数组的索引（0-based or 1-based）是最容易出错的地方。务必明确每个数组的含义。
LCP数组定义不清：务必记住 LCP[i] 比较的是 SA[i] 和 SA[i-1]，而不是 SA[i] 和 SA[i+1]。实现时初始循环通常从 i=1 开始。
倍增算法的边界处理：在比较 rank[i+k] 时，当 i+k >= n，必须赋予一个比所有有效排名都小的值（如-1），否则排序会出错。
暴力解法思维：初学者容易想到用两个循环遍历所有后缀对来求LCP，这是 O(n²) 的，会超时。必须使用线性的Kasai算法。
忽略优化：在倍增算法中，当一轮排序后所有后缀的排名都唯一了，就可以提前结束，避免不必要的循环。

6. 小结

后缀数组（SA） 是原始字符串所有后缀按字典序排序后的起始位置数组，是处理字符串问题的强大索引结构。
最长公共前缀数组（LCP） 描述了排序后相邻后缀的相似程度，是连接SA与具体问题的桥梁。
倍增算法 是构建SA的经典高效算法，其思想是“从小到大，逐步倍增”，利用上一轮的排名结果加速下一轮排序。
Kasai算法 可以在 O(n) 时间内，结合SA和原串计算出LCP数组。
应用场景：后缀数组和LCP数组共同用于高效解决最长重复子串、最长公共子串、模式匹配、不同子串计数等问题。在下一课中，我们将学习其“近亲”——后缀树，它以树形结构提供了更直观的视角和某些场景下更优的灵活性。

练习编辑器

rust