SPOJ1811最长公共子串问题(后缀自动机)

发布时间:2014-10-22 13:35:28编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"SPOJ1811最长公共子串问题(后缀自动机)",主要涉及到SPOJ1811最长公共子串问题(后缀自动机)方面的内容,对于SPOJ1811最长公共子串问题(后缀自动机)感兴趣的同学可以参考一下。

题目:http://www.spoj.com/problems/LCS/   题意:给两个串A和B,求这两个串的最长公共子串。   分析:其实本题用后缀数组的DC3已经能很好的解决,这里我们来说说利用后缀自动机如何实现。 对于串A和B,我们先构造出串A的后缀自动机,那么然后用B串去匹配,对于B,我们一位一位地扫描,维护一个ans值,表示从 B串的开始到B[i]的这个子串与A的最长公共子串。   假设现在到B[i-1]的最长公共子串长度为ans,然后我们来看B[i],如果当前节点有B[i]这个孩子,那么直接就len++即可。 如果没有就找一直向前找pre,直到找到有B[i]这个孩子的节点。   #include <iostream> #include <string.h> #include <algorithm> #include <stdio.h> using namespace std; const int N=250005; struct State { State *pre,*go[26]; int step; void clear() { pre=0; step=0; memset(go,0,sizeof(go)); } }*root,*last; State statePool[N*2],*cur; void init() { cur=statePool; root=last=cur++; root->clear(); } void Insert(int w) { State *p=last; State *np=cur++; np->clear(); np->step=p->step+1; while(p&&!p->go[w]) p->go[w]=np,p=p->pre; if(p==0) np->pre=root; else { State *q=p->go[w]; if(p->step+1==q->step) np->pre=q; else { State *nq=cur++; nq->clear(); memcpy(nq->go,q->go,sizeof(q->go)); nq->step=p->step+1; nq->pre=q->pre; q->pre=nq; np->pre=nq; while(p&&p->go[w]==q) p->go[w]=nq, p=p->pre; } } last=np; } char A[N],B[N]; int main() { int n,m; scanf("%s%s",A,B); n=strlen(A); m=strlen(B); init(); for(int i=0; i<n; i++) Insert(A[i]-'a'); int ans=0,len=0; State *p=root; for(int i=0; i<m; i++) { int x=B[i]-'a'; if(p->go[x]) { len++; p=p->go[x]; } else { while(p&&!p->go[x]) p=p->pre; if(!p) p=root,len=0; else len=p->step+1,p=p->go[x]; } ans=max(ans,len); } printf("%d\n",ans); return 0; }  


上一篇:百度绿萝算法打击友链交易
下一篇:bug05

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款