动态规划&字符串：最长公共子串

时间：2022-02-14 09:21:49

还是直接上转移方程：

动态规划&字符串：最长公共子串

动规只能解决O（n^2）的最长公共子串问题

使用后缀数组或者SAM可以高效地解决这个问题

所以，对于这个问题，动规的代码就不给出了

直接给出SAM的实现，也为以后学习SAM打下一个基础

具体做法是，对一个串建后缀自动机，把另一个串在自动机上跑，维护一下最大的匹配的长度就好了

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int n,ans;

 char s[];

 struct Node

 {

     int siz,rt,last;

     int fa[],maxl[];

     int ch[][];

     Node(){siz=rt=last=;}

     int newnode(int x)

     {

         maxl[++siz]=x;

         return siz;

     }

     void add(int x,int i)

     {

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

         while(p&&ch[p][i]==) ch[p][i]=np,p=fa[p];

         if(p==) fa[np]=rt;

         else

         {

             int q=ch[p][i];

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

             else

             {

                 int r=newnode(maxl[p]+);

                 memcpy(ch[r],ch[q],sizeof(ch[r]));

                 fa[r]=fa[q];

                 fa[q]=fa[np]=r;

                 while(p&&ch[p][i]==q)

                     ch[p][i]=r,p=fa[p];

             }

         }

         last=np;

     }

     void solve()

     {

         int p=rt,len=;

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

         {

             while(p&&ch[p][s[i]-'a']==)

                 p=fa[p],len=maxl[p];

             if(p==) p=rt,len=;

             else p=ch[p][s[i]-'a'],len++;

             ans=max(ans,len);

         }

     }

 }sam;

 int main()

 {

     scanf("%s",s+);

     n=strlen(s+);

     for(int i=;i<=n;i++) sam.add(i,s[i]-'a');

     scanf("%s",s+);

     n=strlen(s+);

     sam.solve();

     printf("%d",ans);

     return ;

 }

我在敲的时候有一种不舒适的感觉，可能是SAM太强大了，日后赶紧学习一波

相关文章