P3809 【模板】后缀排序
题目链接
https://www.luogu.org/problemnew/show/P3809
题目背景
这是一道模板题。
题目描述
读入一个长度为 n n n 的由大小写英文字母或数字组成的字符串，请把这个字符串的所有非空后缀按字典序从小到大排序，然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为 1 1 1 到 n n n。
输入输出格式
输入格式：
一行一个长度为 n n n 的仅包含大小写英文字母或数字的字符串。
输出格式：
一行，共n个整数，表示答案。
输入输出样例
输入样例#1：
ababa
输出样例#1：
5 3 1 4 2
Hint
$n le10^6 $
题解
后缀数组模板题，我将其封装了，所以多了个求lcp的功能这题用不到。
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 1000050
template<typename T>void read(T&x)
{
ll k=0; char c=getchar();
x=0;
while(!isdigit(c)&&c!=EOF)k^=c=='-',c=getchar();
if (c==EOF)exit(0);
while(isdigit(c))x=x*10+c-'0',c=getchar();
x=k?-x:x;
}
void read_char(char &c)
{while(!isalpha(c=getchar())&&c!=EOF);}
struct SuffixArray
{
string s;
int n,c[N],t1[N],t2[N];
int kth[N],rk[N],mm[N],he[N][21];
void BuildKth()
{
int *x=t1,*y=t2;
n=s.size()-1;
int m=300;
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++)c[x[i]=s[i]]++;
for(int i=1;i<=m;i++)c[i]+=c[i-1];
for(int i=n;i>=1;i--)kth[c[x[i]]--]=i;
for(int k=1;k<n;k<<=1)
{
int p=0;
memset(c,0,sizeof(c));
for(int i=n-k+1;i<=n;i++)y[++p]=i;
for(int i=1;i<=n;i++)if (kth[i]-k>0)y[++p]=kth[i]-k;
for(int i=1;i<=n;i++)c[x[y[i]]]++;
for(int i=1;i<=m;i++)c[i]+=c[i-1];
for(int i=n;i>=1;i--)kth[c[x[y[i]]]--]=y[i];
swap(x,y);
p=0;
x[kth[1]]=++p;
for(int i=2;i<=n;i++)
x[kth[i]]=y[kth[i]]==y[kth[i-1]]&&y[kth[i]+k]==y[kth[i-1]+k]?p:++p;
m=p;
if (m==n)break;
}
}
void GetHeight()
{
for(int i=1;i<=n;i++)rk[kth[i]]=i;
mm[1]=0;
for(int i=2;i<=n;i++)mm[i]=mm[i>>1]+1;
int k=0;
for(int i=1;i<=n;i++)
{
if (k)k--;
int j=kth[rk[i]-1];
while(s[i+k]==s[j+k]&&i+k<n&&j+k<n)k++;
he[rk[i]][0]=k;
}
for(int i=1;i<=20;i++)
for(int j=1;j+(1<<i)-1<=n;j++)
he[j][i]=min(he[j][i-1],he[j+(1<<(i-1))][i-1]);
}
int Lcp(int x,int y)
{
x=rk[x]+1; y=rk[y];
if (x>y)swap(x,y);
int k=mm[y-x+1];
return min(he[x][k],he[y-(1<<k)+1][k]);
}
}A;
int main()
{
#ifndef ONLINE_JUDGE
freopen("aa.in","r",stdin);
#endif
ios::sync_with_stdio(false);
cin>>A.s; A.s='!'+A.s;
A.BuildKth();
for(int i=1;i<=A.n;i++)
printf("%d ",A.kth[i]);
}