后缀自动机题目,第一次接触,一点也不会,查资料也不是很清楚,只能算是拷贝的代码了
#include <cstdio> #include <cstdlib> struct node { int l,r,pos; }; struct Str { Str *par,*next[26]; int Sum; void clear() { Sum=0,par=NULL; for(int i=0; i<26; ++i) next[i]=NULL; } }; Str st[4010],*root,*last; node _n[10010]; char s[2010]; int ans[10010]; int len; int cmp(const void *p1,const void *p2) { if(((node *)p1)->l!=((node *)p2)->l) return ((node *)p1)->l - ((node *)p2)->l; else return ((node *)p1)->r - ((node *)p2)->r; } void add(int cur) { Str *p=last,*np=&st[len++]; np->clear(); np->Sum=p->Sum+1; for(; p&&!p->next[cur]; p=p->par) p->next[cur]=np; if(!p) np->par=root; else { Str *q=p->next[cur]; if(p->Sum+1==q->Sum) np->par=q; else { Str *nq=&st[len++]; *nq=*q; nq->Sum=p->Sum+1; nq->par=q->par; np->par=q->par=nq; for(; p&&p->next[cur]==q; p=p->par) p->next[cur]=nq; } } last=np; } int solve() { int Sum=0; for(int i=1; i<len; ++i) Sum+=st[i].Sum-st[i].par->Sum; return Sum; } int main() { //freopen("in.txt","r",stdin); int t,m,x,y; scanf("%d",&t); while(t--) { scanf("%s",s); scanf("%d",&m); for(int i=1; i<=m; ++i) { scanf("%d%d",&x,&y); _n[i].l=x-1,_n[i].r=y-1,_n[i].pos=i; } qsort(_n+1,m,sizeof(node),cmp); _n[0].l=-1; for(int i=1; i<=m; ++i) if(_n[i-1].l!=_n[i].l) { len=0; root=last=&st[len++]; root->clear(); for(int j=_n[i].l; j<=_n[i].r; ++j) add(s[j]-'a'); ans[_n[i].pos]=solve(); } else { if(_n[i].r==_n[i-1].r) ans[_n[i].pos]=ans[_n[i-1].pos]; else { for(int j=_n[i-1].r+1; j<=_n[i].r; ++j) add(s[j]-'a'); ans[_n[i].pos]=solve(); } } for(int i=1; i<=m; ++i) printf("%d\n",ans[i]); } return 0; }