首页 > 代码库 > 【spoj1811 & spoj1812 - LCS1 & LCS2】sam
【spoj1811 & spoj1812 - LCS1 & LCS2】sam
spoj1811 给两个长度小于100000的字符串 A 和 B，求出他们的最长公共连续子串。
先将串 A 构造为 SAM ，然后用 B 按如下规则去跑自动机。
用一个变量 lcs 记录当前的最长公共子串，初始化为0。
设当前状态结点为 p，要匹配的字符为 c，若 go[c] 中有边，说明能够转移状态，则转移并 lcs++；
若不能转移则将状态移动到 p 的 par ，如果仍然不能转移则重复该过程直到 p 回到根节点，并将 lcs 置为 0；
如果在上一个过程中进入了能够转移的状态，则设 lcs 为当前状态的 val。
为什么失配后要移向 par 呢？因为在状态 p 上失配说明该状态的 [min,max] 所表示字符串都不是 B 中的子串，但是比它们短的后缀仍有可能是 B 的子串，而 par 指针恰好指向了该状态的后缀。
spoj1812 要求多个串的最长公共子串,n<=100000,10个串。
本来想用广义sam，然后对每个点位压10位表示它能到哪些串，最后dfs一遍。
20*10^5=10^6个点，时间压得很紧直接超时。
参照上题做法，就把一个串A放进去，nlcs[x]维护当前串与A在自动机的x节点匹配的最大长度，lcs[x]维护前i个串。做完一个串后for一遍，x没有走到过的点lcs[x]=0，其余的lcs[x]=minn(lcs[x],nlcs[x]);
spoj1811
#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>using namespace std;const int N=2*100010;char a[N],b[N];int al,bl,tot,last,son[N][30],step[N],pre[N];int maxx(int x,int y){return x>y ? x:y;}int add_node(int x){ step[++tot]=x; return tot;}void extend(int ch){ int p=last,np=add_node(step[p]+1); while(p && !son[p][ch]) son[p][ch]=np,p=pre[p]; if(!p) pre[np]=1; else { int q=son[p][ch]; if(step[q]==step[p]+1) pre[np]=q; else { int nq=add_node(step[p]+1); memcpy(son[nq],son[q],sizeof(son[q])); pre[nq]=pre[q]; pre[q]=pre[np]=nq; while(son[p][ch]==q) son[p][ch]=nq,p=pre[p]; } } last=np;}int main(){ freopen("a.in","r",stdin); // freopen("me.out","w",stdout); memset(son,0,sizeof(son)); memset(pre,0,sizeof(pre)); memset(step,0,sizeof(step)); tot=0;add_node(0);last=1; scanf("%s%s",a+1,b+1); al=strlen(a+1),bl=strlen(b+1); for(int i=1;i<=al;i++) extend(a[i]-‘a‘+1); int ch,x=1,ans=0,len=0; for(int i=1;i<=bl;i++) { ch=b[i]-‘a‘+1; while(x && !son[x][ch]) x=pre[x],len=step[x]; if(x==0) x=1; if(son[x][ch]) x=son[x][ch],len++; ans=maxx(ans,len); } printf("%d\n",ans); return 0;}
spoj1812
#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>using namespace std;const int N=2*100010;char s[15][N];int n,tot,last,son[N][30],step[N],pre[N],lcs[N],nlcs[N],l[15];bool vis[N];struct node{ int x,y,next;}a[2*N];int maxx(int x,int y){return x>y ? x:y;}int minn(int x,int y){return x<y ? x:y;}int add_node(int x){ step[++tot]=x;lcs[tot]=x; return tot;}void extend(int ch){ int p=last,np=add_node(step[p]+1); while(p && !son[p][ch]) son[p][ch]=np,p=pre[p]; if(!p) pre[np]=1; else { int q=son[p][ch]; if(step[q]==step[p]+1) pre[np]=q; else { int nq=add_node(step[p]+1); memcpy(son[nq],son[q],sizeof(son[q])); pre[nq]=pre[q]; pre[q]=pre[np]=nq; while(son[p][ch]==q) son[p][ch]=nq,p=pre[p]; } } last=np;}void solve(int id){ memset(nlcs,0,sizeof(nlcs)); memset(vis,0,sizeof(vis)); int x=1,len=0,ch; for(int i=1;i<=l[id];i++) { ch=s[id][i]-‘a‘+1; while(x && !son[x][ch]) { x=pre[x],len=step[x],vis[x]=1; nlcs[x]=maxx(nlcs[x],len); } if(x==0) x=1,vis[1]=1; if(son[x][ch]) x=son[x][ch],vis[x]=1,len++; nlcs[x]=maxx(nlcs[x],len); } for(int i=1;i<=tot;i++) if(!vis[i]) lcs[i]=0; else lcs[i]=minn(lcs[i],nlcs[i]);}int main(){ freopen("a.in","r",stdin); // freopen("me.out","w",stdout); memset(son,0,sizeof(son)); memset(pre,0,sizeof(pre)); memset(step,0,sizeof(step)); tot=0;add_node(0);last=1;n=0; while(scanf("%s",s[++n]+1)!=EOF) { l[n]=strlen(s[n]+1); }n--; for(int i=1;i<=l[1];i++) extend(s[1][i]-‘a‘+1); for(int i=2;i<=n;i++) solve(i); int ans=0; for(int i=1;i<=tot;i++) ans=maxx(ans,lcs[i]); printf("%d\n",ans); return 0;}
【spoj1811 & spoj1812 - LCS1 & LCS2】sam
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。