后缀数组小结

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

首先,来看一些定义:

后缀数组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