今天终于学会了后缀数组模板qwq
不过只会模板emmmm
首先我们有一本蓝书emmmmmm
然后看到蓝书221页代码之后我就看不懂了
于是请出rqy
rqy：
一开始那是个对单个字符排序的操作啊
c[i]表示值为i的字符有多少个
x[i]表示第i个位置的优先级是多少
sa[i]表示优先级是i的字符位置
然后第一行明显是初始化，第二行明显就是统计字符个数
至于第三行为什么要求前缀和呢
我们思考优先级越小的排的越靠前
所以说，设优先级是0的有c[0]个，优先级是1的有c[1]个，以此类推
所以说我们有c[0]个字符假设是'0'，应该排到[ 0,c[0] )区间左闭右开
然后截下来有c[1]个字符假设是'1'，应该排到[ c[0],c[0]+c[1] )区间左闭右开
然后以此类推
所以我们简记一下c的前缀和，记为S
于是我们排序的区间就变成了[0,S[0]) [S[0],S[1]) [S[1],S[2])
等等等等。
然后就可以愉快的基数排序啦
然后考虑我们怎么搞两个关键字的排序
就是我先把第二关键字排上，然后保证排序算法稳定的情况下排第一关键字
第二关键字我可以直接枚举排。第一关键字……基数排序可以搞定qwq。
然后看相邻的两个后缀编号是否相等，如果相等说明没能把它们区分开，接着排，如果不相等就可以退出了。
#include<cstdio> #include<algorithm> #include<cctype> #include<cstring> #include<cstdlib> #define maxn 2000100 using namespace std; inline long long read(){ long long num=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)){ num=num*10+ch-'0'; ch=getchar(); } return num*f; } char s[maxn]; int sa[maxn]; int x[maxn]; int y[maxn]; int c[maxn]; int len; void build(int m){ for(int i=0;i<=m;++i) c[i]=0; for(int i=1;i<=len;++i) c[x[i]=s[i]]++; for(int i=1;i<=m;++i) c[i]+=c[i-1]; for(int i=len;i>=1;--i) sa[c[x[i]]--]=i; for(int k=1;k<=len;k<<=1){ int p=0; for(int i=len-k+1;i<=len;++i) y[++p]=i; for(int i=1;i<=len;++i) if(sa[i]>k) y[++p]=sa[i]-k; for(int i=0;i<=m;++i) c[i]=0; for(int i=1;i<=len;++i) c[x[y[i]]]++; for(int i=1;i<=m;++i) c[i]+=c[i-1]; for(int i=len;i>=1;--i) sa[c[x[y[i]]]--]=y[i]; std::swap(x,y); p=1; x[sa[1]]=1; for(int i=2;i<=len;++i) x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p:++p; if(p>=len) break; m=p; } } int main(){ scanf("%s",s+1); len=strlen(s+1); build(200); for(int i=1;i<=len;++i) printf("%d ",sa[i]); return 0; }