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 | 起点 0 | b 在 a 后 |
| na、nana | 起点 4、2 | 最终 SA=[5,3,1,0,4,2] |
窄屏可左右滑动表格,阅读完整计算与理由。
索引保存位置,不必存储每个后缀的完整副本。
04为什么这个方法成立
- 长度 k 前缀已由排名准确区分与排序。
- 两个相邻 k 块的排名二元组,等价于长度 2k 前缀的字典比较。
- 倍增覆盖整个字符串后,排名就是完整后缀次序。
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从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
'aaaa' 的 SA 是什么?
需要一点提示
短后缀是长后缀前缀。
查看解析与答案
[3,2,1,0]。
'ana' 在 banana 哪些位置?
需要一点提示
看以 ana 开头的连续后缀。
查看解析与答案
下标 1、3,对应 SA 中相邻的两项。
为什么不能用 rank[i]+rank[i+k] 当排序键?
需要一点提示
相加丢失先后主次。
查看解析与答案
(1,3) 与 (2,2) 和相同但字典序不同,需要有序二元组而非简单加和。