SA算法入门

后缀数组是什么?

以下用\(S_i\)表示字符串S的[i...n]子串部分
对于一个字符串S的所有后缀,即所有 \(S_i\), 按字典序进行排序

我们可以求出两个东西:
一个叫 rank[i], 指\(S_i\)在所有后缀中的排名
一个叫 sa[i] , 指排名为i的后缀的是\(S_{sa[i]}\)

后缀数组怎么求

我们可以考虑使用倍增的思想求解

利用字符串字典序的特性 (先比较高位再比较低位)

具体来说, 求解时先求出当前长度 len 时的答案
即: 每个 S[i...min(i+len-1,n)] 的排名与位置的双射
然后递推出长度为 \(2*len\) 时的情况
比较过程可用基数排序实现