首页 > 代码库 > SPOJ_LCS

SPOJ_LCS

2024-07-08 19:57:20   219人阅读

经典题目，求两个串的最长公共子串。

是这样来做的。

以第一个串构造SAM，第二个串在自动机上跟新一遍就可以了。

更新的过程是这样的，假设当前到达的状态点为x（初始状态为0点），下一个字符是c，如果当前状态没有c这条边就一直沿着pre指针走，直到找到第一个有c这条边的状态或者确认全部都没有。

更新是这样的，用一个数字保存上一次状态的最大长度tmp，现在到达了一个新的状态了，显然这个状态一定保证在第二个串出现，因为我是从第二个串里面一个一个字符地添加进来的，那么只要保证满足第一个串（即模式串）就可以了。怎么保证呢？只要不大于tmp不大于该状态的step值就可以了。为什么？因为能到达当前状态的话说明是可以存在这个长度的。tmp与step比较并且去较小值。就完成了更新了。

嗯其实还听简单的。

代码君上了：

 

#include <iostream>#include <cstdio>#include <cstring>#define maxn 600300using namespace std;int next[maxn][26],pre[maxn],step[maxn];int N=0,last=0,n,p,q,np,nq;char s[maxn];void insert(int x,int m){	p=last,np=++N;	for (int i=0; i<26; i++) next[N][i]=0; pre[N]=0; step[N]=0;	step[np]=m;	for (;p!=-1 && next[p][x]==0; p=pre[p]) next[p][x]=np;	last=np;	if (p==-1) return;	q=next[p][x];	if (step[q]==step[p]+1) { pre[np]=q; return; }	nq=++N;	for (int i=0; i<26; i++) next[N][i]=0; pre[N]=0; step[N]=0;	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;	}int dfs(){	int ans=0,tmp=0;	for (int i=1,cur=0; s[i]; i++)	{		int k=s[i]-‘a‘;		while (next[cur][k]==0 && cur!=0) cur=pre[cur];		if (step[cur]<tmp) tmp=step[cur];		cur=next[cur][k];		if (cur) tmp++;		ans=max(ans,tmp);	}	return ans;}int main(){	pre[0]=-1;	for (int i=0; i<26; i++) next[0][i]=0; step[0]=0;	scanf("%s",s+1);	for (int i=1; s[i]; i++) insert(s[i]-‘a‘,i);	scanf("%s",s+1);	printf("%d\n",dfs());	return 0;}

 

　　

 

 


联系
我们