后缀数组学习笔记

是这种做法下每次比较两个后缀需要二分哈希单次比较(log⁡)O(logn)总排序需要(log⁡)O(nlogn)次比较因此整体复杂度是(log⁡2)O(nlog2n)的比较慢。考虑能否优化发现直接每个独立比较太慢了由于所有的都在一个字符串上可以考虑倍增的思想。我们倍增字符串长度那么我们可以先得到所有长度为 11 时的排名之后对于长度为 22 时先比较前面一个字符如果相同再比较后面一个字符以此类推。所以做法就是假设我们现在处理长度最长为 22x 时的排名那么先比较两个串的前 x 位如果相等再比较后 x 位。显然这是一个双关键字排序那么就可以直接通过基数排序优化到(log⁡)O(nlogn)了。虽然有其它神秘科技但是这个做法在比赛时应该已经够了也是经典的后缀数组求法。我们用sai​表示排名为 i 的后缀起始位置用rki​表示后缀起始位置为 i 的排名直接根据基数排序即可完成。但是实际上可能需要一些常数优化放一个我写的好像部分处理不是很常规最长公共前缀最长公共前缀也被称为LCP。通过结合后缀数组可以快速处理一个字符串后缀的最长公共前缀查询这也是一个后缀数组的经典应用。一个显然的结论一个后缀肯定和自己字典序排名相邻的后缀的 LCP 最长。假设有一个更长的但排名不是相邻的那么其字典序一定其和相邻的两个之间矛盾即可证得。那么我们可以通过求相邻的情况再进行区间查询得到这一段里面的最小值。显然由于我们保证了相邻每一个都尽量大了最小值也就是其前缀没有变过的最长位置。那么只需要处理出每个相邻的结果之后再使用st 表即可快速查询了。显然相邻的并不难求有非常简单的(log⁡)O(nlogn)写法就是有点麻烦。但是有非常好写的()O(n)做法。设ℎ[]LCP([[]..],[[−1]..])h[i]LCP(s[sa[i]..n],s[sa[i−1]..n])即排名相邻的两个后缀的最长公共前缀长度。对于原串中以位置 i 开头的后缀其排名为 []rk[i]我们想要求出 ℎ[[]]h[rk[i]]。有一个关键性质ℎ[[]]≥ℎ[[−1]]−1h[rk[i]]≥h[rk[i−1]]−1直观理解后缀 [−1..]s[i−1..n] 与排名前一位的后缀 [[[−1]−1]..]s[sa[rk[i−1]−1]..n] 有长度为 ℎ[[−1]]h[rk[i−1]] 的公共前缀。去掉这两个后缀的第一个字符后我们得到后缀 [..]s[i..n] 和后缀 [[[−1]−1]1..]s[sa[rk[i−1]−1]1..n]它们的公共前缀长度至少为 ℎ[[−1]]−1h[rk[i−1]]−1。而后缀 [..]s[i..n] 在排名上可能与后者不相邻但它的排名前一位即 [[]−1]sa[rk[i]−1]的 LCP 长度不会小于这个值。由于每次都只减少一否则都是增加且这个增加上限也是 n 的级别所以时间复杂度()O(n)是一