(题目链接)

题意

　　求多个串的最长公共子串

Solution

　　对其中一个串构造后缀自动机，然后其它串在上面跑匹配。对于每个串都可以跑出在SAM上的每一个节点的最长公共子串的长度，当然，有些节点虽然匹配时可能没有经过，但是在parent树上它的儿子却被经过了，作为儿子的后缀，那么这些节点显然也是被经过的，所以我们需要用parent树上的儿子节点去更新其父亲节点。完成之后，我们再对全局的匹配长度进行更新（取min）。

　　爱神：对于SAM初学，要深刻理解出现次数向父亲传递，接收串数从儿子获取这句话。这里的父亲是parent树上的父亲，儿子是SAM图上的后继节点。

代码

// spoj LCS2#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #define LL long long#define inf 1<<30#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std; const int maxn=100010;char s[maxn];namespace SAM { int Dargen,sz,last,n; int par[maxn<<1],len[maxn<<1],ch[maxn<<1][26],mat[maxn<<1],f[maxn<<1]; int b[maxn],id[maxn<<1]; void Extend(int c) { int np=++sz,p=last;last=np; len[np]=len[p]+1; for (;p && !ch[p][c];p=par[p]) ch[p][c]=np; if (!p) par[np]=Dargen; else { int q=ch[p][c]; if (len[q]==len[p]+1) par[np]=q; else { int nq=++sz;len[nq]=len[p]+1; memcpy(ch[nq],ch[q],sizeof(ch[q])); par[nq]=par[q]; par[np]=par[q]=nq; for (;p && ch[p][c]==q;p=par[p]) ch[p][c]=nq; } } } void build() { last=sz=Dargen=1; n=strlen(s+1); for (int i=1;i<=n;i++) Extend(s[i]-'a'); } void pre() { for (int i=1;i<=sz;i++) b[len[i]]++; for (int i=1;i<=n;i++) b[i]+=b[i-1]; for (int i=1;i<=sz;i++) id[b[len[i]]--]=i; for (int i=1;i<=sz;i++) mat[i]=inf; } void match() { int n=strlen(s+1); int ll=0; for (int i=1;i<=sz;i++) f[i]=0; for (int p=Dargen,i=1;i<=n;i++) { while (p>1 && !ch[p][s[i]-'a']) p=par[p],ll=len[p]; if (ch[p][s[i]-'a']) { p=ch[p][s[i]-'a']; f[p]=max(f[p],++ll); } } for (int i=sz;i>=1;i--) if (f[id[i]]) f[par[id[i]]]=len[par[id[i]]]; for (int i=1;i<=sz;i++) mat[i]=min(mat[i],f[i]); } int query() { int ans=0; for (int i=1;i<=sz;i++) ans=max(ans,mat[i]); return ans; }}using namespace SAM;int main() { scanf("%s",s+1); build(); pre(); while (scanf("%s",s+1)!=EOF) match(); printf("%d",query()); return 0;}