SPOJ1812 && bzoj2946 [后缀自动机]

题目

LCS2 - Longest Common Substring II

A string is finite sequence of characters over a non-empty finite set Σ. In this problem, Σ is the set of lowercase letters. Substring, also called factor, is a consecutive sequence of characters occurrences at least once in a string. Now your task is a bit harder, for some given strings, find the length of the longest common substring of them. Here common substring means a substring of two or more strings.

输入

The input contains at most 10 lines, each line consists of no more than 100000 lowercase letters, representing a string.

输出

The length of the longest common substring. If such string doesn’t exist, print “0” instead.

样例输入

alsdfkjfjkdsal fdjskalajfkdsla aaaajfaaaa

样例输出

2

分析

这道题是spoj1811的加强版,求多个串的最长公共子串,思路和上一题一样,对第一个输入的串建一个后缀自动机,其他的串在自动机上面匹配,匹配时记录每个位置能匹配到的最大值,每次更新ans为对应位置上最大值的最小值.需要注意的是当走到一个点时要更新它的所有父亲节点的maxs值,原因很简单,经过Tsort()后整个序列是按maxl由小到大排布的,这样可以看成他们的parent树由父亲到儿子节点的过程,这样逆序循环一遍,同时更新父亲节点的信息既可.

完整代码

#include<bits/stdc++.h> #define maxn 200010 //#define DEBUG using namespace std; int n,answer=0; int ans[maxn],tmp[maxn],sum[maxn],maxs[maxn]; char ch[maxn]; struct SAM { int root,tot,last; int son[maxn][26],fa[maxn],maxl[maxn]; void init() { root=tot=last=1; memset(son,0,sizeof(son)); memset(fa,0,sizeof(fa)); memset(maxl,0,sizeof(maxl)); } void add(int pos) { int x=ch[pos]-'a'; int np=++tot,p=last; last=np,maxl[np]=maxl[p]+1; for( ; p&&!son[p][x] ; p=fa[p] ) son[p][x]=np; if(!p) fa[np]=root; else { int q=son[p][x]; if(maxl[q]==maxl[p]+1) fa[np]=q; else { int nq=++tot; maxl[nq]=maxl[p]+1; memcpy(son[nq],son[q],sizeof(son[q])); fa[nq]=fa[q]; fa[q]=fa[np]=nq; for( ; son[p][x]==q ; p=fa[p] ) son[p][x]=nq; } } } void sort() { for(int i=1;i<=tot;++i) sum[maxl[i]]++; for(int i=1;i<=n;++i) sum[i]+=sum[i-1]; for(int i=1;i<=tot;++i) tmp[sum[maxl[i]]--]=i; #ifdef DEBUG for (int i=1;i<=tot;i++) printf("tmp[%d]=%d dis[tmp[%d]]=%d\n",i,tmp[i],i,maxl[tmp[i]]); #endif } void build() { init(); scanf("%s",ch+1); n=strlen(ch+1); for(int i=1;i<=n;++i) add(i); for(int i=1;i<=tot;++i) ans[i]=maxl[i]; sort(); } void update() { for(int i=tot;i>0;i--) { int x=tmp[i]; ans[x]=min(ans[x],maxs[x]); if(maxs[x]&&fa[x]) maxs[fa[x]]=maxl[fa[x]]; } } void work() { memset(maxs,0,sizeof(maxs)); int len=0,p=root; for(int i=1;i<=n;++i) { int x=ch[i]-'a'; if(son[p][x]) len++,p=son[p][x]; else { for( ; p&&!son[p][x] ; p=fa[p] ) ; if(!p) len=0,p=root; else len=maxl[p]+1,p=son[p][x]; } maxs[p]=max(maxs[p],len); } update(); } } sam ; int main() { memset(ans,0,sizeof(ans)); sam.build(); while(scanf("%s",ch+1)==1) { n=strlen(ch+1); sam.work(); } #ifdef DEBUG for(int i=1;i<=sam.tot;++i) printf("ans[%d]=%d\n",i,ans[i]); #else for(int i=1;i<=sam.tot;++i) answer=max(answer,ans[i]); #endif printf("%d",answer); } /* alsdfkjfjkdsal fdjskalajfkdsla aaaajfaaaa -------------- 2 */

参考资料

http://blog.csdn.net/thy_asdf/article/details/51569443