P3809【模板】后缀排序

传送门

深入理解了一波后缀数组，这东西真的很妙诶，自己推感觉完全不现实，看来只能靠背代码了
这段时间就多敲敲，把板子记熟吧
代码：

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; void read(int &x) {char ch; bool ok;for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x; } #define rg register const int maxn=1e6+10; char p[maxn];int n,m=maxn,a[maxn],sa[maxn],x[maxn],q[maxn],num; int main() {scanf("%s",p+1);n=strlen(p+1);for(rg int i=1;i<=n;i++)a[x[i]=p[i]]++;for(rg int i=1;i<=m;i++)a[i]+=a[i-1];for(rg int i=n;i;i--)sa[a[x[i]]--]=i;for(rg int k=1;k<=n;k<<=1,num=0){for(rg int i=n-k+1;i<=n;i++)q[++num]=i;for(rg int i=1;i<=n;i++)if(sa[i]>k)q[++num]=sa[i]-k;for(rg int i=1;i<=m;i++)a[i]=0;for(rg int i=1;i<=n;i++)a[x[i]]++;for(rg int i=1;i<=m;i++)a[i]+=a[i-1];for(rg int i=n;i;i--)sa[a[x[q[i]]]--]=q[i];for(rg int i=1;i<=n;i++)q[i]=x[i];num=x[sa[1]]=1;for(rg int i=2;i<=n;i++)if(q[sa[i]]!=q[sa[i-1]]||q[sa[i]+k]!=q[sa[i-1]+k])x[sa[i]]=++num;else x[sa[i]]=num;if(num>=n)break;m=num;}for(rg int i=1;i<=n;i++)printf("%d ",sa[i]); }

转载于:https://www.cnblogs.com/lcxer/p/10418125.html

总结

以上是生活随笔为你收集整理的P3809【模板】后缀排序的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。