专题进阶 · 字符串算法推荐总顺序 · 第 89 / 148 课

用后缀排序把子串搜索转为有序查找,理解倍增排名与 LCP 的作用。

先学会这些,再进入本课 字符串 二分查找 基数排序
还有 3 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 字符串算法

后缀数组Suffix Array

按字典序排列所有后缀的位置,配合 LCP 支持重复子串和模式检索。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

用后缀排序把子串搜索转为有序查找,理解倍增排名与 LCP 的作用。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

字符串 'banana' 中重复片段很多,怎样把所有后缀排成一个可检索索引?

02一步步得到方法

后缀数组只保存起点下标

banana 的后缀包括 banana、anana、nana、ana、na、a。按字典序排列后,记录原起点得到 SA=[5,3,1,0,4,2]。相同模式作为前缀的后缀会连续出现,所以可二分找到匹配范围。

直接用所有切片排序容易理解,却会复制 O(n²) 字符。本课用倍增:先按一个字符排名,再用两段长度 k 的排名二元组比较长度 2k 前缀。

已排名的小块拼成更长块

每轮键为 (rank[i],rank[i+k]),越界第二段用 −1,使短后缀排在以它为前缀的更长后缀前。排序后给相同键同一个新排名,再令 k*=2。

排名全部互异时,已经区分全部后缀,可以结束。LCP 数组还可记录相邻后缀的最长公共前缀,例如 a 与 ana 为 1、ana 与 anana 为 3,支持重复子串等进一步查询。

排序的是后缀起点,不是复制全部后缀

后缀数组保存原串各后缀的起始下标,按对应后缀字典序排列。倍增法用两个已知长度块的排名比较更长前缀,避免每次都从头逐字符比较整个后缀。

当所有排名唯一时,后缀顺序已经确定;否则继续倍增长度。LCP 是相邻后缀公共前缀长度的另一组信息,需要另算,不能把后缀数组本身说成已包含所有子串答案。

03把一个小例子完全算清楚

s='banana'。

步骤计算与状态为什么这样做
最短 a起点 5排第一
ana、anana起点 3、1短前缀先于长前缀
banana起点 0b 在 a 后
na、nana起点 4、2最终 SA=[5,3,1,0,4,2]

窄屏可左右滑动表格,阅读完整计算与理由。

索引保存位置,不必存储每个后缀的完整副本。

04为什么这个方法成立

  1. 长度 k 前缀已由排名准确区分与排序。
  2. 两个相邻 k 块的排名二元组,等价于长度 2k 前缀的字典比较。
  3. 倍增覆盖整个字符串后,排名就是完整后缀次序。

05把推导翻译成代码

Python · 可独立运行的教学实现

def suffix_array(s):
    n = len(s)
    sa, rank, k = list(range(n)), list(map(ord,s)), 1
    while k < n:
        def key(i):
            return rank[i], rank[i+k] if i+k < n else -1
        sa.sort(key=key)
        new = [0]*n
        for j in range(1,n):
            new[sa[j]] = new[sa[j-1]] + (key(sa[j]) != key(sa[j-1]))
        rank = new
        if n and rank[sa[-1]] == n-1:
            break
        k *= 2
    return sa

逐个理解关键决定

else -1
越界相当于更小的结束标记,不可用普通字符排名 0 混淆。
key(sa[j]) != key(sa[j-1])
相同前缀应得到相同排名,不能无条件按位置递增。

06时间、空间与实现范围

本版本每轮比较排序 O(n log n),共 O(log n) 轮,总 O(n log² n),空间 O(n)。

用计数/基数排序二元组可做到 O(n log n);不要把优化版成本标在本代码上。朴素二分模式比较还要乘模式字符比较成本。

07改变条件,检查哪里会出错

认为 SA 已直接给出所有重复子串

还需要相邻公共前缀等信息,输出全部重复子串本身可能很大。

使用比较排序却套用计数排序版本的界

本课每轮比较排序为 O(n log n),约 log n 轮,故 O(n log² n);更快构造需要额外实现。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

'aaaa' 的 SA 是什么?

需要一点提示

短后缀是长后缀前缀。

查看解析与答案

[3,2,1,0]。

练习 2 · 边界与辨析

'ana' 在 banana 哪些位置?

需要一点提示

看以 ana 开头的连续后缀。

查看解析与答案

下标 1、3,对应 SA 中相邻的两项。

练习 3 · 变式与迁移

为什么不能用 rank[i]+rank[i+k] 当排序键?

需要一点提示

相加丢失先后主次。

查看解析与答案

(1,3) 与 (2,2) 和相同但字典序不同,需要有序二元组而非简单加和。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Princeton · 字符串算法

理解之后,继续递进

继续当前专题:字符串哈希 →。跨专题先修要求会在下一课顶部提示。

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。