什么是后缀数组?

假设我们现在有一个字符串"ababa"
我们知道这个数组有一些后缀,分别是(以下后缀i指以i为开头的后缀)

1 2 3 4 5
ababa baba aba ba a

现在我们按照字典序将它们排序,得到:5 3 1 4 2,那么我们令$SA_1=5,SA_2=3,SA_3=1...$便得到了后缀数组SA

如何求后缀数组?

给一道例题:洛谷P3809
主要思想是倍增,可以结合图,文字说明和代码进行查看。
后缀数组
假设现在我们已经排序完成了所有长度为num的子串,并得到了当前子串们的SA(排完序后的顺序)和$x_i$(又称rank,即以i开头的子串的排名)
现在我们的任务是排序所有长度为num+num的子串,那么,我们令一个这样的子串由两个长度为num的子串A和B组成。现在,我们的任务是以A为第一关键字,B为第二关键字进行基数排序
定义$y_i$:第二关键字排名为i的子串开头的位置,以下步骤是求出$y_i$:

1.对于末尾溢出的子串,它们的第二关键字为0,对它们进行处理。
2.对于所有长度为num的子串,如果它们的开头大于num,则可以作为一个长度为num+num的子串的第二关键字,然后根据它们的SA来求一些$y_i$



然后,求出新的SA值。

1.开一个桶T,将每个关键字2对应的关键字1塞进桶里。
2.利用每个关键字2对应的关键字1的排名,更新SA(即基数排序)



最后,求出新的$x_i$。这个只要利用SA就行了,同时还要利用上一次的$x_i$,用于对比两个子串是否相同,进行去重。
由于子串长度溢出末尾就补0这个操作,所以最后一次我们排序的n个子串一定是所有后缀了。
完整代码实现就是:



后缀的最长前缀

$Height_i$:排名为i和i-1的两个后缀的最长公共前缀
$H_i$:后缀i和排名在其前面的后缀的最长公共前缀
我们可以证明一个性质:$H_i \geq H_{i-1}-1$
假设后缀k是后缀i-1的前一名,最长前缀就是$H_{i-1}$,去掉一个字符,变成了后缀k+1和后缀i。
如果$H_{i-1}$等于0或1,$H_i \geq 0$显然成立
否则,k+1一定是i的前一名,则$H_{i-1} \leq H_i$
于是我们可以O(n)计算$Height_i$啦!



后缀数组的基本应用

洛谷P2408:每一个子串必定是一个后缀的前缀。我们把后缀i与后缀i-1的公共前缀看作是后缀i独有的子串,那么答案就是$\sum_i^n (n-SA_i+1-Height_i)$
bzoj1717/洛谷P2852:二分答案ans。如果在Height数组中,连续的大于等于ans的数大于等于K-1个(因为K-1个Height对应K个子串嘛),说明当前答案可行,否则不可行。
bzoj1692/洛谷P2870:比较从队首与队尾的字母字典序大小,如果一样,就要依次比较。所以干脆将原串翻转过来粘在后面,然后求这个长度为2n的新串的后缀数组,依次贪心比较获得答案。
spoj220:把所有的串粘在一起,中间用不同的特殊字符隔开(这样简单方便一些)。二分答案ans,扫描Height数组,提取其中$Height_i \geq ans$的区间[l,r],对于所有i属于$[SA_{l-1},SA_r]$,是否其中在每个字符串中最小和最大的之间相差大于等于ans,如果是,则该答案为合法。
bzoj2258/poj2758:题解戳我
HDU3948:把字符串改成跑manacher要用的形式,然后用manacher搞出每一个字符向左和右可以得到的回文长度p,再求出字符串的SA和Height。然后每个字符造成的贡献是$(p[SA_i]-min(Height_i,p[SA_{last}]))/2$,这个last是指,如果以某个字符为中心的回文串,被完全包括在了上一个字符为中心的回文串中,那么就跳过这个字符,用这种方式得到的上一个字符。