[Poi2000]公共串 && hustoj2797

传送门：http://begin.lydsy.com/JudgeOnline/problem.php?id=2797

题目大意：给你几个串求出几个串中的最长公共子串。

题解：先看n最大才5，所以很容易想到暴力写法，因为最近在学后缀自动机就写写后缀自动机吧。

　　　我们将第一个串作为母串，然后在用其他的串与它进行匹配，并且记录下其匹配中每个状态的最大匹配数，答案则为每个状态的最大匹配的最小值中的最大值。。（绕晕了）

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #define N 4005

 using namespace std;

 int last,root,tot;

 char s[N];

 int n,m,ans;

 struct data{

     int son[N][],fa[N],val[N],ans[N],sum[N],tmp[N],smin[N];

     void prepare(){root=last=tot=;}

     int newnode(int x){val[++tot]=x; return tot;}

     void extend(int x)

     {

         int p=last,np=newnode(val[p]+);

         for (; p && !son[p][x]; p=fa[p]) son[p][x]=np;

         if (!p) fa[np]=root;

         else

         {

             int q=son[p][x];

             if (val[p]+==val[q]) fa[np]=q;

             else

             {

                 int nq=newnode(val[p]+);

                 memcpy(son[nq],son[q],sizeof(son[q]));

                 fa[nq]=fa[q]; fa[q]=fa[np]=nq;

                 for (; p&& son[p][x]==q; p=fa[p]) son[p][x]=nq;

             }

         }

         last=np;

     }

     void sort()

     {

         memset(sum,,sizeof(sum));

         for (int i=; i<=tot; i++) ans[i]=val[i];

         for (int i=; i<=tot; i++) sum[val[i]]++;

         for (int i=; i<=tot; i++) sum[i]+=sum[i-];

         for (int i=; i<=tot; i++) tmp[sum[val[i]]--]=i;

     }

     void work()

     {

         scanf("%s",s+); m=strlen(s+);

         memset(smin,,sizeof(smin));int len=;last=root;

         for (int i=; i<=m; i++)

         {

             int x=s[i]-'a';

             if (son[last][x]) last=son[last][x],len++;

             else

             {

                 for (; last&&!son[last][x];)last=fa[last];

                 if (!last) len=,last=root;

                 else

                 {

                     len=val[last]+; last=son[last][x];

                 }

             }

             smin[last]=max(smin[last],len);

         }

         for (int i=tot; i>=; i--)

         {

             int x=tmp[i];

             ans[x]=min(ans[x],smin[x]);

             if (fa[x] && smin[x]) smin[fa[x]]=val[fa[x]];

         }

     }

 }SAM;

 int main()

 {

     scanf("%d\n",&n); n--;

     SAM.prepare();

     scanf("%s",s+); int len=strlen(s+);

     for (int i=; i<=len; i++) SAM.extend(s[i]-'a');

     SAM.sort();

     for (int i=; i<=n; i++) SAM.work();

     for (int i=; i<=tot; i++) ans=max(ans,SAM.ans[i]);//,cout<<i<<" "<<SAM.ans[i]<<endl;

     printf("%d\n",ans);

 }

注意：我们在写的过程中，每到一个状态我们要不断跟新之前的状态答案，我们可以用dfs或者利用right数组的特性来更新，具体细节看看代码。