【题目链接】 http://www.spoj.com/problems/LCS/en/

【题目大意】

    求两个串的最长公共子串。

【题解】

    好像用后缀自动机解的话没什么技巧性，一个串建后缀自动机，一个串跑貌似就可以了？（滑稽）

【代码】

#include <cstdio>
#include <cstring>
#include <algorithm> 
using namespace std;
const int N=500005;
char s[N];
struct sam{
	  int ans,p,q,np,nq,cnt,last,a[N][26],l[N],f[N];
	  sam(){ans=cnt=0;last=++cnt;}
	  void extend(int c){
		    p=last;np=last=++cnt;l[np]=l[p]+1;
		    while(!a[p][c]&&p)a[p][c]=np,p=f[p];
		    if(!p)f[np]=1;
		    else{
			      q=a[p][c];
			      if(l[p]+1==l[q])f[np]=q;
			      else{
				        nq=++cnt;l[nq]=l[p]+1;
				        memcpy(a[nq],a[q],sizeof(a[q]));
				        f[nq]=f[q]; f[np]=f[q]=nq;
				        while(a[p][c]==q)a[p][c]=nq,p=f[p];
			      }
		    }
	  }
	  void build(){
		    scanf("%s",s+1);
		    int len=strlen(s+1);
		    for(int i=1;i<=len;i++)extend(s[i]-'a');
	  }
	  void solve(){
		    scanf("%s",s+1);
		    int len=strlen(s+1),now=1,tmp=0,p=1;
		    for(int i=1;i<=len;i++){
			      int c=s[i]-'a';
			      if(a[p][c])p=a[p][c],tmp++;
			      else{
				        while(p&&!a[p][c])p=f[p];
				        if(!p)p=1,tmp=0;
				        else tmp=l[p]+1,p=a[p][c];
			      }ans=max(ans,tmp);
		    }printf("%d\n",ans);
	  }
}sam;
int main(){
	  sam.build();
	  sam.solve();
	  return 0;
}

• 相关文章
• 全局相关文章