后缀数组⼊门（⼀）——后缀排序前⾔
后缀数组这个东西早就有所⽿闻，但由于很难，学了好⼏遍都没学会。
最近花了挺长⼀段时间去研究了⼀下，总算是勉强学会了⽤倍增法来实现后缀排序（据说还有⼀种更快的DC3法，但是要难得多）。数组定义
⾸先，为⽅便起见，我们⽤后缀i表⽰从下标i开始的后缀。（相信⼤家都知道后缀是什么的）
⾸先，我们需要定义⼏个数组：
s：需要进⾏后缀排序的字符串。
SA i：记录排名为i的后缀的位置。
rk i：记录后缀i的排名。
pos i：同样记录排名为i的后缀的位置。
tot i：⽤于基数排序，统计i的排名。
要注意理解这些数组的定义，这样才能明⽩后⾯的内容。
第⼀次操作
⾸先，让我们来⼀步步模拟⼀下第⼀次操作。
我们第⼀步是要将每个后缀按照第1个字符进⾏排序。
这应该还是⽐较简单的，不难发现可以初始化得到rk i=s i,pos i=i。
然后我们对其进⾏第⼀次排序。
注意，排序最好⽤O(n)的基数排序，⽤sort的话会多⼀个log。
具体的⼀些关于基数排序的细节可以见下。
关于基数排序
后缀排序中的基数排序，其实相当于将⼆元组(rk i,pos i)进⾏排序。
⾸先，第⼀步⾃然是清空tot数组。
加1。
然后，从1到n枚举，将tot rk
i
接下来是⼀遍累加，求出每⼀个元素的排名。
然后从n到1倒序枚举，更新SA数组即可。
接下来的操作
接下来⾃然是要对每个后缀前2个字符进⾏排序了。
暴⼒的⽅法就是再重新排序⼀遍。
但实际上，在确定了第1个字符的⼤⼩关系后，我们就不需要如此⿇烦了。
因为后缀i的第2个字符，实际上就是后缀i+k的第1个字符。
因此我们通过第⼀次排序，就可以直接确定第2个字符的⼤⼩关系了。
于是我们就可以重新⽤pos数组将这个⼤⼩关系记录下来，再次排序。
然后就是按照这种⽅法来倍增处理第4个字符、第8个字符、第16个字符... ...
重复此操作直⾄所有后缀各不相同即可。
这样的总复杂度就是O(nlogn)的了。
具体实现还是有很多细节的，实在没理解的可以根据代码再研究⼀下。
代码（）
class Class_SuffixSort//后缀排序
{
private:
int n,SA[N+5],rk[N+5],pos[N+5],tot[N+5];
inline void RadixSort(int S)//基数排序，S表⽰字符集⼤⼩
{
register int i;
for(i=0;i<=S;++i) tot[i]=0;//清空数组
for(i=1;i<=n;++i) ++tot[rk[i]];//从1到n枚举，将tot[rk[i]]加1
for(i=1;i<=S;++i) tot[i]+=tot[i-1];//累加
for(i=n;i;--i) SA[tot[rk[pos[i]]]--]=pos[i];//倒序枚举，更新SA数组
}
public:
inline void Solve(char *s)
{
register int i,k,cnt=0,Size=122;//初始化字符集⼤⼩为122（即'z'的ASCII码）
for(n=strlen(s),i=1;i<=n;++i) rk[pos[i]=i]=s[i-1];//初始化rk数组和pos数组
字符串长度排序for(RadixSort(Size),k=1;cnt<n;Size=cnt,k<<=1)//先是⼀遍基数排序，然后倍增枚举k，直⾄所有后缀各不相同
{
for(cnt=0,i=1;i<=k;++i) pos[++cnt]=n-k+i;//将长度⼩于等于k的后缀先加⼊数组中，此时的cnt相当于计数器
for(i=1;i<=n;++i) SA[i]>k&&(pos[++cnt]=SA[i]-k);//对于排名⼤于k的字符串，将其加⼊数组中
for(RadixSort(Size),i=1;i<=n;++i) pos[i]=rk[i];//基数排序⼀遍，然后将rk数组的值全部赋值给pos数组
for(rk[SA[1]]=cnt=1,i=2;i<=n;++i) rk[SA[i]]=(pos[SA[i-1]]^pos[SA[i]]||pos[SA[i-1]+k]^pos[SA[i]+k])?++cnt:cnt;//利⽤SA数组来得到rk，此时的cnt存储不同的字符串个数，从⽽得到排名            }
for(i=1;i<=n;++i) F.write(SA[i]),F.writec(' ');//输出答案
}
}S;
Processing math: 100%

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。