QAQ学了好几天了…（我太傻啦）
#include<cstdio> #include<cstring> #define rep(i,n) for(register int i=1;i<=n;i++) const int N=40006; const int S=26; int n,cnt,last,T; int suf[N],val[N],tr[N][S+3]; char s[N]; inline int newNode(int x) { val[++cnt]=x;return cnt; } inline void insert(int x) { int p=last,np=newNode(val[p]+1);memset(tr[np],0,sizeof tr[np]); while(p&&!tr[p][x])tr[p][x]=np,p=suf[p]; if(!p)suf[np]=1; else { int q=tr[p][x]; if(val[q]==val[p]+1)suf[np]=q; else { int nq=newNode(val[p]+1); memcpy(tr[nq],tr[q],sizeof tr[nq]); suf[nq]=suf[q];suf[np]=suf[q]=nq; while(p&&tr[p][x]==q)tr[p][x]=nq,p=suf[p]; } } last=np; } inline void solve() { int u=1; rep(i,n)for(register int j=0;j<S;j++) if(tr[u][j]){u=tr[u][j];break;} printf("%d ",val[u]-n+1); } int main() { scanf("%d",&T); while(T--) { scanf("%s",s+1);n=strlen(s+1);last=cnt=1; memset(tr[1],0,sizeof tr[1]); rep(i,n)insert(s[i]-'a');rep(i,n)insert(s[i]-'a'); solve(); } return 0; }