首页 > 代码库 > SPOJ_LCS2
SPOJ_LCS2
和上个题目差不多,这次是找若干个串的LCS,若干<=10 。
做法上面也是类似的。
首先以第一个建立SAM,然后后面的串都在上面更新。每个串的更新是独立进行的,互不影响。对于同一状态,首先在同一个串的更新中取最大值,然后再不同的串之间取最小值,最后统计一下所有状态的最大值就可以了。
与上面不同的是,多了一个小小的操作,对于某一个状态存在一个匹配长度x,那么在该状态上所有的pre指针所指向的状态的的匹配长度都肯定会是step值。
一开始我也不理解为什么,后来发现后缀自动机的性质啦嘿嘿,(想一想就知道咯)。
但是为什么不更新pre指针会错呢?其实是这样的,每次加入一个字符匹配,当前只可能在一个状态,但是其实pre指针所有的位置都是可以进行匹配的。而且由于串很多,所有后面的串不一定都更新在这个状态,虽然他们的right位置是一样的。。(嗯,好像很有道理)
为什么上一个题目lcs没有对pre指针进行更新却依然正确呢?原因是不需要,对于每个状态step相当于与第一个模式串比配的最大长度,注意是最大,所以在第二个字符串来匹配的时候,当前状态的长度就是两个串在该状态的最大公共长度了。同时,在该状态的所有pre状态也肯定会存在匹配长复,但是那些肯定都不会优于这个状态,所以这个更新是不必要的,而对于多个串,由于每个串在可能分别落在不同的pre指针上,所以需要跟新一遍咯。
召唤代码君:
#include <iostream>#include <cstdio>#define maxn 200100using namespace std;int next[maxn][26],pre[maxn],step[maxn];int f[13][maxn];int N=0,last=0,n=1;int p,q,np,nq;char s[13][maxn];void insert(int x,int m){ np=++N,p=last,step[np]=m; while (p!=-1 && next[p][x]==0) next[p][x]=np,p=pre[p]; last=np; if (p==-1) return; q=next[p][x]; if (step[q]==step[p]+1) { pre[np]=q; return ; } nq=++N,step[nq]=step[p]+1,pre[nq]=pre[q]; for (int i=0; i<26; i++) next[nq][i]=next[q][i]; pre[np]=pre[q]=nq; for (; p!=-1 && next[p][x]==q;p=pre[p]) next[p][x]=nq;}void dp(int x){ int cur=0,tmp=0; for (int i=0; s[x][i]; i++) { int k=s[x][i]-‘a‘; while (next[cur][k]==0 && cur!=0) cur=pre[cur]; tmp=min(step[cur],tmp); cur=next[cur][k]; if (cur) tmp++; f[x][cur]=max(f[x][cur],tmp); } for (int i=N; i>0; i--) if (f[x][i]) for (int j=pre[i];j && f[x][j]!=step[j];j=pre[j]) f[x][j]=step[j];}int main(){ pre[0]=-1; while (scanf("%s",s[n])!=EOF) n++; n--; for (int i=0; s[1][i]; i++) insert(s[1][i]-‘a‘,i+1); for (int i=2; i<=n; i++) dp(i); int ans=0; for (int i=1; i<=N; i++) { int tmp=step[i]; for (int j=2; j<=n; j++) tmp=min(tmp,f[j][i]); ans=max(ans,tmp); } printf("%d\n",ans); return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。