题目背景
这是一道模板题。
题目描述
读入一个长度为 \(n\) 的由大小写英文字母或数字组成的字符串，请把这个字符串的所有非空后缀按字典序从小到大排序，然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为 \(1\) 到 \(n\) 。
输入输出格式
输入格式：
一行一个长度为 nn 的仅包含大小写英文字母或数字的字符串。
输出格式：
一行，共n个整数，表示答案。
输入输出样例
输入样例#1：
ababa
输出样例#1：
5 3 1 4 2
说明
\(n <= 10^6\)
题解
模板题，不想说什么了，SA的代码是真的难理解
#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
const int MAXN=1000000+10;
int SA[MAXN],n,m,cnt[MAXN],rk[MAXN],nxt[MAXN];
char s[MAXN];
template<typename T> inline void read(T &x)
{
T data=0,w=1;
char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();
x=data*w;
}
template<typename T> inline void write(T x,char ch='\0')
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
if(ch!='\0')putchar(ch);
}
template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}
template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}
template<typename T> inline T min(T x,T y){return x<y?x:y;}
template<typename T> inline T max(T x,T y){return x>y?x:y;}
inline void GetSA()
{
n=strlen(s+1);
int m=300;
for(register int i=1;i<=n;++i)rk[i]=s[i];
for(register int i=1;i<=n;++i)cnt[rk[i]]++;
for(register int i=1;i<=m;++i)cnt[i]+=cnt[i-1];
for(register int i=n;i>=1;--i)SA[cnt[rk[i]]--]=i;
for(register int k=1,ps;k<=n;k<<=1)
{
ps=0;
for(register int i=n-k+1;i<=n;++i)nxt[++ps]=i;
for(register int i=1;i<=n;++i)
if(SA[i]>k)nxt[++ps]=SA[i]-k;
for(register int i=1;i<=m;++i)cnt[i]=0;
for(register int i=1;i<=n;++i)cnt[rk[i]]++;
for(register int i=1;i<=m;++i)cnt[i]+=cnt[i-1];
for(register int i=n;i>=1;--i)SA[cnt[rk[nxt[i]]]--]=nxt[i];
std::swap(nxt,rk);
rk[SA[1]]=1;ps=1;
for(register int i=2;i<=n;rk[SA[i]]=ps,++i)
if(nxt[SA[i-1]]!=nxt[SA[i]]||nxt[SA[i-1]+k]!=nxt[SA[i]+k])ps++;
if(ps>=n)break;
m=ps;
}
}
int main()
{
scanf("%s",s+1);
GetSA();
for(register int i=1;i<=n;++i)write(SA[i],' ');
puts("");
return 0;
}