后缀数组详解

参照博客

后缀数组

定义： 后缀就是从字符串的某个位置i到字符串末尾的子串，我们定义以s的第i个字符为第一个元素的后缀为(suff(i))

辅助数组：

(sa_i)：表示排名为(i)的后缀的起始位置的下标

(rk_i)：表示起始位置的下标为(i)的后缀的排名

(x_i)：表示起始位置的下标为(i)的后缀的第一关键字

(y_i)：表示起始位置的下标为(i)的后缀的第二关键字

后缀数组的思想：

先说最暴力的情况，快排(O(nlogn))每个后缀，但是这是字符串，所以比较任意两个后缀的复杂度其实是(O(n))，这样一来就是接近(O(n^2logn))的复杂度，数据大了肯定是不行的，所以我们这里有两个优化。

倍增： 每次以前(2^k)为第一关键字，后(2^k)为第二关键字（没有的补零）进行合并，预处理出按第一个字符排序的情况，当最后每个后缀的排名都不同时，排序完成

基数排序： 简单来说，就是个桶

代码具体流程：

1. 按第一个字符排序

for (register int i = 1;i <= n;i++) ++c[x[i] = s[i]];
for (register int i = 1;i <= m;i++) c[i] += c[i-1];
for (register int i = n;i >= 1;i--) sa[c[x[i]]--] = i;

举个例子：

[abbac
]