题目大意:给你n个串,求它们的最长公共子串 n<=10,每个串<=100000
这题是后缀自动机的论文题
具体的做法是,先以第一个串做一个后缀自动机,然后用剩下的每个串去匹配就行了
具体来说,就是用每个串都像lcs那样去做就行了,然后把每个节点可以扩展的最长长度记录下来,再用儿子更新父亲,就OK了
#include<cmath> #include<cstdio> #include<cstring> #include<cassert> #include<iostream> #include<algorithm> using namespace std; const int maxn=100011; char s[maxn]; int n; void init(){scanf("%s",s); n=strlen(s);} struct Tsam{ struct Tnode{ Tnode *ch[26],*f; int ml,nl; void clear(){memset(ch,0,sizeof(ch)); f=NULL; ml=nl=0;} }e[maxn<<1],*root,*last; int tot; Tnode *newnode(){e[tot].clear(); return e+(tot++);} void clear(){tot=0; root=last=newnode();} void add(int c){ Tnode *np=newnode(),*p=last; for (np->ml=p->ml+1,last=np;p && !p->ch[c];p=p->f) p->ch[c]=np; if (!p) return np->f=root,void(); Tnode *q=p->ch[c]; if (q->ml==p->ml+1) return np->f=q,void(); Tnode *r=newnode(); *r=*q; r->ml=p->ml+1; for (q->f=np->f=r;p && p->ch[c]==q;p=p->f) p->ch[c]=r; } }sam; void work(){ static int ws[maxn]; static Tsam::Tnode *tp[maxn<<1]; sam.clear(); for (int i=0;i<n;++i) sam.add(s[i]-'a'); for (int i=0;i<=n;++i) ws[i]=0; for (int i=0;i<sam.tot;++i) ++ws[sam.e[i].ml]; for (int i=1;i<=n;++i) ws[i]+=ws[i-1]; for (int i=sam.tot-1;i>=0;--i) tp[--ws[sam.e[i].ml]]=sam.e+i; int ans; while (scanf("%s",s)!=EOF){ Tsam::Tnode *now=sam.root; for (int i=0,res=0;s[i];++i){ int c=s[i]-'a'; if (now->ch[c]) ++res,now=now->ch[c]; else{ for (;now && !now->ch[c];now=now->f); if (!now) now=sam.root,res=0; else res=now->ml+1,now=now->ch[c]; } if (res>now->nl) now->nl=res; } for (int i=sam.tot-1;i>=0;--i){ Tsam::Tnode *x=tp[i]; if (x->ml>x->nl) x->ml=x->nl; if (x->f && x->f->nl<x->nl) x->f->nl=x->nl; x->nl=0; } } ans=0; for (int i=1;i<sam.tot;++i) if (sam.e[i].ml>ans) ans=sam.e[i].ml; cout<<ans<<endl; } int main(){ init(); work(); return 0; }
还有一点要注意,如果不用ml来存每个扩展最大的最小值,在用儿子更新父亲的时候,就要判断有没有超过父亲的ml,WA了好久。。。