后缀数组小结

发表于

最近开始学习后缀数组了，在这里做一个总结。

首先，来看一些定义：

后缀数组SA：是一个1到n的排列，它保证Suffix(SA[i]) < Suffix(SA[i + 1])，也就是将S的n个后缀从小到大排列。
名次数组Rank：保存的是以i开头的后缀在所有后缀中的位置（即名次）。
高度数组height：表示SA[i]和SA[i - 1]的最长前缀。

易知SA和Rank互为逆运算。即SA[Rank[i]] = i;

SA和Rank的求法

  1. 设排序的当前长度为h，Suffix(i, h)表示Suffix(i)的前h个字符
  2. 先按H = 1对Suffix(i, H)进行排序。
  3. 倍增H，利用之前排好的$\frac{H}{2}$长度的rank数组作为关键字，把后$\frac{H}{2}$部分作为第二关键字，把前$\frac{H}{2}$部分作为第一关键字，对H长度的子串排序。

模板：

1
2