算法模板——后缀数组

后缀数组是什么&＃xff1f;可以吃吗&＃xff1f;
不可以吃&＃xff0c;它是给一个字符串的所有后缀进行排序的算法。
如&＃xff1a;一个字符串aabaaaab&＃xff0c;它的后缀排好序后起始位置分别是&＃xff1a;4 5 6 1 7 2 8 3
显然如果暴力去排序时间复杂度为O(n2)&＃xff0c;可以用倍增算法或DC3算法来解决&＃xff0c;本文主要介绍倍增算法&＃xff08;我才不会告诉你其实是我不会DC3算法呢&＃xff09;。
接下来定义如下几个数组&＃xff1a;

引用大佬图解&＃xff1a;

倍增法的主要内容&＃xff1f;
每次对长度为2k的串进行排序时都可以利用两个连续的长为2k−1的串排序的结果来进行排序&＃xff0c;当2k>&＃61;n时&＃xff0c;每个串都是以这个串的起点为起点的后缀。
再次引用大佬图解&＃xff1a;

这张图是什么意思呢&＃xff1f;
就是&＃xff1a;x和y分别作为第一关键字和第二关键字&＃xff0c;进行排序&＃xff0c;以这一次排序的结果作为下一次排序的参考。
怎么排序&＃xff1f;
需要排序的范围不超过n&＃xff0c;当然是选择计数排序&＃xff08;基数排序&＃xff0c;桶排序&＃xff09;啊。
时间复杂度&＃xff1f;
O(nlogn)&＃xff0c;如果不使用计数排序就是O(nlog2n)
代码
温馨提示&＃xff1a;复制到记事本上并将tab键调成8格效果更佳

#include
#include const int maxn&＃61;100000;char s[(maxn<<1)&＃43;10];
int sa[(maxn<<1)&＃43;10],rank[(maxn<<1)&＃43;10],tmp[(maxn<<1)&＃43;10];
int sum[(maxn<<1)&＃43;10],a[(maxn<<1)&＃43;10],n;inline int swap(int *&x,int *&y)//指针swap
{int *t&＃61;x;x&＃61;y;y&＃61;t;return 0;
}inline int suffix_sort()
{int *x&＃61;rank,*y&＃61;tmp,m&＃61;26;//先排序for(register int i&＃61;1; i<&＃61;n; &＃43;&＃43;i){x[i]&＃61;a[i];y[i]&＃61;i;&＃43;&＃43;sum[x[i]];}for(register int i&＃61;1; i<&＃61;m; &＃43;&＃43;i){sum[i]&＃43;&＃61;sum[i-1];}for(register int i&＃61;n; i; --i){sa[sum[x[i]]]&＃61;i;--sum[x[i]];}int len&＃61;1,p&＃61;1;while(p0;//每次循环设一下初值&＃xff0c;然后排序for(register int i&＃61;n-len&＃43;1; i<&＃61;n; &＃43;&＃43;i){&＃43;&＃43;p;y[p]&＃61;i;}for(register int i&＃61;1; i<&＃61;n; &＃43;&＃43;i){if(sa[i]-len>0){&＃43;&＃43;p;y[p]&＃61;sa[i]-len;}}//前面是按第二关键字排序&＃xff0c;接下来按第一关键字排序for(register int i&＃61;0; i<&＃61;m; &＃43;&＃43;i){sum[i]&＃61;0;}for(register int i&＃61;1; i<&＃61;n; &＃43;&＃43;i){&＃43;&＃43;sum[x[y[i]]];}for(register int i&＃61;1; i<&＃61;m; &＃43;&＃43;i){sum[i]&＃43;&＃61;sum[i-1];}for(register int i&＃61;n; i; --i){sa[sum[x[y[i]]]]&＃61;y[i];--sum[x[y[i]]];}swap(x,y);//现在y数组已经没有用了p&＃61;1;x[sa[1]]&＃61;1;//下一个步骤是去重for(register int i&＃61;2; i<&＃61;n; &＃43;&＃43;i){if(!((y[sa[i-1]]&＃61;&＃61;y[sa[i]])&&(y[sa[i-1]&＃43;len]&＃61;&＃61;y[sa[i]&＃43;len]))){&＃43;&＃43;p;}x[sa[i]]&＃61;p;}len<<&＃61;1;}//如果所有的都已经排好序&＃xff0c;那么就没有必要排下去了&＃xff0c;退出p&＃61;0;//在上面计算的步骤中x数组记录的值可能不是真正的rank数组&＃xff0c;需要重新计算for(register int i&＃61;1; i<&＃61;n; &＃43;&＃43;i){&＃43;&＃43;p;rank[sa[i]]&＃61;p;}return 0;
}int main()
{scanf("%s",s&＃43;1);n&＃61;strlen(s&＃43;1);for(register int i&＃61;1; i<&＃61;n; &＃43;&＃43;i){a[i]&＃61;s[i]-&＃39;a&＃39;&＃43;1;}suffix_sort();for(register int i&＃61;1; i<&＃61;n; &＃43;&＃43;i){printf("%d\n",sa[i]);}return 0;
}