后缀指从某个位置开始到字符串末尾的一个子串,用suffix(i)来表示。
后缀数组(suffix array)指将s的所有后缀从小到大排序后,取其下标i放入数组中,该数组就叫做后缀数组。
![sa[i]](https://51itzy.com/uploads/202412/23/d8d6e00325d3a7fb.jpg)
讯享网表示排名为i的后缀为![suffix(sa[i])](https://51itzy.com/uploads/202412/23/d8d6e00325d3a7fb.jpg)
排名数组指suffix(i)在后缀数组中的排名(下标)
表示suffix(i)的排名为![rank[i]](https://51itzy.com/uploads/202412/23/d8d6e00325d3a7fb.jpg)
后缀数组和排名数组是互逆的,可以来回转换。
![sa[rank[i]]=i;](https://51itzy.com/uploads/202412/23/d8d6e00325d3a7fb.jpg)
suffix(i)排在第
位,排在第
位的后缀来自
;
![rank[sa[i]]=i;](https://51itzy.com/uploads/202412/23/d8d6e00325d3a7fb.jpg)
排在第
位的后缀来自
,suffix(t)排在第
位。

构建后缀数组有两种算法,DC3算法和倍增算法。一般n<=1e6时采用码量较小的倍增算法。此处采用倍增算法。
算法思路
对字符串从每个下标开始的长度为
的子串进行排序,得到排名。k从0开始每次增加1,当
时,从每个下标开始的长度为
的子串都相当于其后缀suffix(i)。每次子串排序利用上一次子串的排名得到。
求解长度为
的子串排名,将上一次rank值的第i个和第i+1个结合,再进行排序,得到新的rank值
当rank值没有相同值时已经得到了后缀排名,因为通过结合的方法前面的字符串已经确定了大小,无需再排序。
最后将rank数组转化为后缀数组,即![suffix[rank[i]]=i;](https://51itzy.com/uploads/202412/23/d8d6e00325d3a7fb.jpg)
算法实现
后缀数组的构建中涉及到排序,因为采用倍增算法,因此长度为n的字符串最多需要
次排序,排序若采用快速排序,则总复杂度为
,而采用基数排序复杂度为
,因此此处采用基数排序
1、将每个字符都转换为数字存入ss[],并通过参数传递赋值给x[]数组(相当于排名数组),进行基数排序。为了防止比较时越界,在末尾用0封装。同时将字符串长度n+1
执行基数排序,的到后缀数组sa[]。
注意:大于等于n的部分的排名应与存在的所有排名不同,因为默认的0是有效的排名(排名从0开始),所以将越界的排名赋为-1
//...该步将s[i]转化为初始排名ss[i] for(int i=0;i<m;i++) c[i]=0; for(int i=0;i<n;i++) c[x[i]=ss[i]]++;//因为初始长度只有1,因此排名直接等于对应的数字 for(int i=1;i<m;i++) c[i]+=c[i-1]; for(int i=n-1;i>=0;i--) sa[--c[x[i]]]=i;//记得倒序放入 for(int i=
讯享网
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/76241.html