后缀数组
复制本地路径 | 在线编辑
重要的是使用场景，而非原理（不过原理也很简单）。
简介
设字符串：S = ababa
构造结构
所有后缀为：
0: ababa
1: baba
2: aba
3: ba
4: a
按字典序排序（得到后缀数组 SA），字典序从小到大排：
4: a
2: aba
0: ababa
3: ba
1: baba
所以后缀数组 SA 就是这些后缀的起始下标：
SA = [4, 2, 0, 3, 1]
字符串匹配
假设我们要查找模式串：P = aba
关键性质：如果 P 在 S 中出现，那么 P 一定是某个后缀的前缀。务必理解这句话，这是核心思想。
使用二分查找，根据 SA 找出字典序排序之后的字符串，每次比较 P 和字符串前缀：
- 下界：第一个 ≥
aba的后缀 → 下标 2 - 上界：最后一个 ≤
aba的后缀 → 下标 0
所以匹配位置是： 2 和 0
总结
二分查找 + 前缀比较
时间复杂度：
- 预处理 SA：O(n) 或 O(n log n)
- 单次匹配：O(|P| log n)
适合：多次查询、大数据量、多模式匹配。
场景
更重要的是使用场景，重点在于他和普通的字符串匹配优势在哪里：
- 多次查询：预处理
S之后，每次查询时间复杂度为 O(|P| log n)，而普通字符串匹配每次查询时间复杂度为 O(n)。 - 匹配最长前缀：这个需要再加一个数组记录，不过不细谈了。
那很显然了，这种结构很适合在大数据上使用，相当于空间换时间。一次预处理之后，以后查询都会很快。比如生物信息学中：
基因组快速匹配。实验测得的基因序列，匹配人类基因组中哪个位置。由于人类基因组很大，所以普通的字符串匹配，每次都会耗时。所以大家就对人类基因组建立一个后缀数组，以后用的时候就下载这个文件，然后用它进行匹配。