坪山城市建设局官方网站,大学科技园东区 做网站,蓝色 宽屏 网站 模板,小程序企业网站开发学习自B站up主 kouylan
定义
后缀是包含最后个字母的子串
把字符串 str 的所有后缀按字典排序#xff0c;sa[i]表示排名为 i 的后缀的开头下标 如何求解SA
倍增的方法
先把每个位置开始的长度为1的子串排序#xff0c;在此基础上再把长度为2的子串排序#xff08;长度…学习自B站up主 kouylan
定义
后缀是包含最后个字母的子串
把字符串 str 的所有后缀按字典排序sa[i]表示排名为 i 的后缀的开头下标 如何求解SA
倍增的方法
先把每个位置开始的长度为1的子串排序在此基础上再把长度为2的子串排序长度为2的子串就 是前面算过的长度为1的子串再加上后面的一位第 i 位的和 i1 再把长度为481632...两个两个拼直到串的末尾也就是排到了后缀。 如何从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)
