题面
https://vjudge.net/problem/SPOJ-DISUBSTR
题解
#include<cstdio> #include<iostream> #include<cstring> #define ri int #define N 1050 using namespace std; int n,T; char s[N]; struct node{ int ff,len; int ch[26]; } t[N<<1]; int tot,last; void extend(int o) { int p,np,q,nq; p=last; np=++tot; last=np; t[np].len=t[p].len+1;//len[np]=len[p]+1; while (p && !t[p].ch[o]) t[p].ch[o]=np,p=t[p].ff; if (!p) t[np].ff=1; else { q=t[p].ch[o]; if (t[q].len==t[p].len+1) { t[np].ff=q; } else { nq=++tot; t[nq]=t[q]; t[nq].len=t[p].len+1; t[np].ff=t[q].ff=nq; while (p && t[p].ch[o]==q) t[p].ch[o]=nq,p=t[p].ff; } } } int main(){ scanf("%d",&T); while (T--) { scanf("%s",s+1); n=strlen(s+1); tot=last=1; memset(t,0,sizeof(t)); for (ri i=1;i<=n;i++) extend(s[i]-65); long long ret=0; for (ri i=1;i<=tot;i++) ret+=t[i].len-t[t[i].ff].len; printf("%lld ",ret); } return 0; }