傳送門

深入理解了一波后綴數組，這東西真的很妙誒，自己推感覺完全不現實，看來只能靠背代碼了
這段時間就多敲敲，把板子記熟吧
代碼：

#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【模板】后缀排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。