BZOJ 2946 Poi2000 公共串 后缀自动机

题目大意：求n个串的最长公共子串

太久没写SAM了真是……

将第一个串建成后缀自动机，用其它的串进去匹配

每个节点记录每个串在上面匹配的最大长度

那么这个节点对答案的贡献就是所有最大长度的最小值

对所有贡献取最大就行了= = 这最大最小看着真是别扭

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #define M 10100 using namespace std; int n,ans; char s[M]; namespace Suffix_Automaton{ struct SAM{ SAM *parent,*son[26]; int max_len,min_len[6]; bool v; SAM(int _=0):parent(0x0),max_len(_),v(false) { memset(son,0,sizeof son); memset(min_len,0,sizeof min_len); } }*root=new SAM,*last=root; void Extend(int x) { SAM *p=last; SAM *np=new SAM(p->max_len+1); while(p&&!p->son[x]) p->son[x]=np,p=p->parent; if(!p) np->parent=root; else { SAM *q=p->son[x]; if(p->max_len+1==q->max_len) np->parent=q; else { SAM *nq=new SAM(p->max_len+1); nq->parent=q->parent; memcpy(nq->son,q->son,sizeof nq->son); q->parent=nq;np->parent=nq; for(;p&&p->son[x]==q;p=p->parent) p->son[x]=nq; nq->min_len[1]=nq->max_len; } } last=np; np->min_len[1]=np->max_len; } void DFS(SAM *p) { int i,temp=0x3f3f3f3f; for(i=1;i<=n;i++) temp=min(temp,p->min_len[i]); ans=max(ans,temp); p->v=true; for(i=0;i<26;i++) if( p->son[i] && !p->son[i]->v ) DFS(p->son[i]); } } int main() { using namespace Suffix_Automaton; int i,j; cin>>n; scanf("%s",s+1); for(i=1;s[i];i++) Extend(s[i]-'a'); for(i=2;i<=n;i++) { scanf("%s",s+1); SAM *p=root;int len=0; for(j=1;s[j];j++) { while( p!=root && !p->son[s[j]-'a'] ) p=p->parent,len=p->max_len; if( p->son[s[j]-'a'] ) p=p->son[s[j]-'a'],len++; for(SAM* temp=p;temp;temp=temp->parent) temp->min_len[i]=max(temp->min_len[i],min(len,temp->max_len) ); } } DFS(root); cout<