[SPOJ1811]Longest Common Substring 后缀自动机最长公共子串

题目链接：http://www.spoj.com/problems/LCS/

题意如题目，求两个串的最大公共子串LCS。

首先对其中一个字符串A建立SAM，然后用另一个字符串B在上面跑。

用一个变量Lcs来记录当前答案，如果能转移到下一个状态则Lcs++。

若不能转移说明需要重新选择状态，则不断地跳到当前状态的fa状态，如果发现能够转移就停下来，Lcs变为当前状态的len+1并转移到下一个可行状态。

这里很像AC自动机的fail指针的跳跃。因为fa状态是当前状态的后缀，已经被匹配过，而fa状态有更多的机会转移。

于是最后的答案就是所有状态下Lcs的最大值。这样做的总体思想是求出对于每一个位置能向前扩展的最大长度。值得注意的是对于一个成功匹配状态s的匹配长度显然也可以作为它fa的匹配长度。因为fa的right集合一定包含了s的right集合，即都包含了当前的Lcs串的结束位置，从s开始向上更新一遍就好了，不过这里好像不需要。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int n,m;

 char a[],b[];

 struct State{

     int ch[],fa,len;

     void init(){

         fa=-;

         len=;

         memset(ch,-,sizeof(ch));

     }

 }T[];

 int cnt=,la;

 void Extend(int c){

     int end=++cnt,tmp=la;

     T[end].init();

     T[end].len=T[tmp].len+;

     while((~tmp)&&(!~T[tmp].ch[c])){

         T[tmp].ch[c]=end;

         tmp=T[tmp].fa;

     }

     if(!~tmp) T[end].fa=;

     else{

         int ne=T[tmp].ch[c];

         if(T[tmp].len+==T[ne].len) T[end].fa=ne;

         else{

             int np=++cnt;

             T[np]=T[ne];

             T[np].len=T[tmp].len+;

             T[end].fa=T[ne].fa=np;

             while((~tmp)&&T[tmp].ch[c]==ne){

                 T[tmp].ch[c]=np;

                 tmp=T[tmp].fa;

             }

         }

     }

     la=end;

 }

 void solve(){

     int ans=;

     T[].init();

     for(int i=;i<=n;i++) Extend(a[i]-'a');

     int Lcs=,o=;

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

         int c=b[i]-'a';

         if(~T[o].ch[c]){

             o=T[o].ch[c];

             ans=max(ans,++Lcs);

         }

         else{

             while((~o)&&(!~T[o].ch[c])) o=T[o].fa;

             if(!~o) o=Lcs=;

             else{

                 Lcs=T[o].len+;

                 o=T[o].ch[c];

                 ans=max(ans,Lcs);

             }

         }

     }

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

 }

 int main(){

     scanf("%s%s",a+,b+);

     n=strlen(a+);

     m=strlen(b+);

     solve();

     return ;

 }

巴特西

[SPOJ1811]Longest Common Substring 后缀自动机最长公共子串

最新文章

热门文章

巴特西

[SPOJ1811]Longest Common Substring 后缀自动机 最长公共子串

最新文章

热门文章

[SPOJ1811]Longest Common Substring 后缀自动机最长公共子串