SPOJ1811 LCS SAM

后缀自动机简单题。

其主要思路是，先对第一个字符串建立后缀自动机，把第二个串放在上面匹配，

若当前状态s有字符x的转移，直接转移len=step+1。

若当前状态s没有向字符x的转移，退回pre_s检查是否有转移，

若没有，则继续退回，否则转移到节点y，len=step_y+1。

以上思路主要利用的是关于pre节点的性质，由于pre节点的right集合是其子节点的right集合的并集，且max(pre)=min(s)-1.

所以从pre节点往上跳的时候，就能找到最长的后缀相同的部分的节点。（不知道这么说对不对）。

与KMP算法的很像。

可以参考这篇博客

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<string>

 #include<cstring>

 #include<cmath>

 #include<ctime>

 #include<algorithm>

 #include<iomanip>

 #include<set>

 #include<map>

 #include<queue>

 using namespace std;

 #define mem1(i,j) memset(i,j,sizeof(i))

 #define mem2(i,j) memcpy(i,j,sizeof(i))

 #define LL long long

 #define up(i,j,n) for(int i=(j);i<=(n);i++)

 #define FILE "dealing"

 #define poi vec

 #define eps 1e-10

 #define db double

 const int maxn=,inf=,mod=;

 int read(){

     int x=,f=,ch=getchar();

     while(x<''||x>''){if(ch=='-')f=-;ch=getchar();}

     while(x<=''&&x>=''){x=(x<<)+(x<<)+ch-'',ch=getchar();}

     return f*x;

 }

 bool cmax(int& a,int b){return a<b?a=b,true:false;}

 namespace sam{

     const int maxn=;

     int pre[maxn],c[maxn][],len[maxn],now,cnt,np,p,q,nq,Len;

     void clear(){mem1(c,);mem1(len,);mem1(pre,);cnt=,now=;}

     void expend(int x){

         np=++cnt;len[np]=len[now]+;p=now;now=np;

         while(p&&!c[p][x])c[p][x]=np,p=pre[p];

         if(!p)pre[np]=;

         else {

             q=c[p][x];

             if(len[q]==len[p]+)pre[np]=q;

             else {

                 len[nq=++cnt]=len[p]+;

                 pre[nq]=pre[q];

                 pre[q]=pre[np]=nq;

                 mem2(c[nq],c[q]);

                 while(p&&c[p][x]==q)c[p][x]=nq,p=pre[p];

             }

         }

     }

     int walk(int x){

         while(!c[now][x]&&pre[now])now=pre[now],Len=len[now];

         if(!c[now][x])return ;

         now=c[now][x];Len++;return Len;

     }

     void build(char* s){

         int n=strlen(s+);

         up(i,,n)expend(s[i]-'a');

     }

 };

 char s[maxn];

 int main(){

     freopen(FILE".in","r",stdin);

     freopen(FILE".out","w",stdout);

     sam::clear();

     scanf("%s",s+);

     sam::build(s);

     scanf("%s",s+);

     int n=strlen(s+);

     int ans=;sam::now=;sam::Len=;

     up(i,,n)cmax(ans,sam::walk(s[i]-'a'));

     cout<<ans<<endl;

     return ;

 }

巴特西

SPOJ1811 LCS SAM

最新文章

热门文章