传送门
妥妥的后缀数组裸题（主要是楼主菜只会打这种题目），还有拓展lucas还没调对qwq菜飞了。。。
求sa和lcp，就是后缀数组求sa和height。
代码：
#include<iostream> #include<stdio.h> #include<string.h> using namespace std; const int Maxn=100005; char a[Maxn]; int tax[Maxn],tp[Maxn],sa[Maxn],rank[Maxn],height[Maxn]; int m=127,n; void Rsort() { for(int i=1;i<=m;i++) tax[i]=0; for(int i=1;i<=n;i++) tax[rank[tp[i]]]++; for(int i=1;i<=m;i++) tax[i]+=tax[i-1]; for(int i=n;i>=1;i--) sa[tax[rank[tp[i]]]--]=tp[i]; } int cmp(int *f,int x,int y,int w) { return (f[x]==f[y])&&(f[x+w]==f[y+w]); } void suffix() { for(int i=1;i<=n;i++) rank[i]=a[i],tp[i]=i; Rsort(); for(int w=1,p=1,i;p<n;w+=w,m=p) { for(p=0,i=n-w+1;i<=n;i++) tp[++p]=i; for(i=1;i<=n;i++) if(sa[i]>w) tp[++p]=sa[i]-w; Rsort(); swap(rank,tp); rank[sa[1]]=p=1; for(int i=2;i<=n;i++) rank[sa[i]]=cmp(tp,sa[i],sa[i-1],w)?p:++p; } for(int i=1,j,p;i<=n;height[rank[i]]=j,i++) for(j=max(height[rank[i-1]]-1,0),p=sa[rank[i]-1];a[p+j]==a[i+j];j++); } int main() { scanf("%s",a+1); n=strlen(a+1); suffix(); for(int i=1;i<=n;i++) printf("%d ",sa[i]); printf("\n"); for(int i=2;i<=n;i++) printf("%d ",height[i]); return 0; }