[acm算法学习] 后缀数组SA

学习自B站up主 kouylan 

定义

后缀是包含最后个字母的子串

把字符串 str 的所有后缀按字典排序，sa[i]表示排名为 i 的后缀的开头下标

如何求解SA

倍增的方法

先把每个位置开始的长度为1的子串排序，在此基础上再把长度为2的子串排序（长度为2的子串就 是前面算过的长度为1的子串再加上后面的一位，第 i 位的和 i+1 ），再把长度为4，8，16，32...（两个两个拼）直到串的末尾，也就是排到了后缀。

如何从2^(k-1) 到 2^k

• 记 rk[i] 表示当前长度下，i 开始的子串的排名
• 前 2^(k-1) 和后  2^(k-1) 拼成了 2^k
• 确定  2^k 的排名时，先比较前 2^(k-1)的rk，如果更小，那么整个也更小，不用比后面了；如果前 2^(k-1)相等，则去比较后  2^(k-1) 的rk

up主给的这个图很形象

原串中下标位置为1的a，会去和原串中下标为2的b拼一起，a(1)和a(6)的rk相同，所以比较后面部分，b(2) 比 c(7) 的 rk 要先，所以最后长度为2的 rk 里ab 比 ac 要前。由于c(7)是最后一位了，所以它的下一位是个空串，我们定义空串的rk是-1，这样，因为没有比空串还小的了，设为-1可以达到效果。

求解程序

sa 是根据 rk 来的，根据排序好的 sa 来更新 rk2 (使用临时变量 rk2)，因为更新的过程中要用到上一次的 rk ，初始的rk是字典序。

用sort在当前 k 下把 sa 数组排好顺序，然后再遍历一遍数组sa把对应位置的字母排名依次排好。最后更新一遍rk。

重载的排序函数，是根据先比前一半，后比后一半。

时间复杂度 n*log(n)*log(n)