原文链接http://www.cnblogs.com/zhouzhendong/p/8982392.html

题目传送门 - SPOJ LCS

题意

　　求两个字符串的最长公共连续子串长度。

　　字符串长$\leq 250000$

题解

　　首先对于第一个字符串建一个$SAM$。

　　然后拿第二个串在$SAM$上面走一遍就好了。

　　具体地：

　　将第二个串的字符一个一个地按照顺序加入。

　　设当前状态为$now$，要加入字符$c$，当前匹配的字符串长度为$len$（答案自然是各种情况下$len$的最大值）。

　　如果在$SAM$上面，状态$now$有标号为$c$的转移，那么，$len=len+1$，$now$更新为转移后的结果。

　　否则，我们跳$now$的$fa$，直到得到一个新的$now$使得$now$有标号为$c$的转移，并使$len=Max(now)+1$，$now$更新为新的$now$再走$c$转移之后的状态。

　　关于上述做法的正确性的叙述：

　　对于第一种情况，相当于在原结果的末尾再加上一个匹配的字符。

　　对于第二种情况，略微复杂一些。首先，跳$fa$的效果其实就是从当前子串中删除前缀，直到匹配串$SAM$的当前状态再一次和被匹配串的当前子串相匹配。注意，由于状态$now$没有标号为$c$的转移，所以被匹配串的之前成功匹配的子串中，有一段前缀现在不能匹配了。所以你找到的第一个有标号为$c$的转移的$now$的祖先的$Max$值必然小于原来的$len$，所以在本次操作之后，新的$len$的值必然不大于原来的$len$。

　　UPD(2018-05-07): 这个第二种情况也可以通过分析后缀自动机性质来理解。这里不展开介绍。

　　首先，很显然这个匹配是成功的。又由于我们每次跳$fa$时候，保留的串长又是尽量长的，所以满足了最大化的要求。

代码

#include <bits/stdc++.h>

using namespace std;

const int N=500005;

int n,last=1,size=1;

char s[N];

struct SAM{

	int Next[26],fa,Max;

}t[N];

void expend(int c){

	int p=last,np=++size,q,nq;

	t[np].Max=t[p].Max+1;

	for (;!t[p].Next[c];p=t[p].fa)

		t[p].Next[c]=np;

	q=t[p].Next[c];

	if (t[q].Max==t[p].Max+1)

		t[np].fa=q;

	else {

		nq=++size;

		t[nq]=t[q],t[nq].Max=t[p].Max+1;

		t[q].fa=t[np].fa=nq;

		for (;t[p].Next[c]==q;p=t[p].fa)

			t[p].Next[c]=nq;

	}

	last=np;

}

int main(){

	t[0].Max=-1;

	for (int i=0;i<26;i++)

		t[0].Next[i]=1;

	scanf("%s",s);

	n=strlen(s);

	for (int i=0;i<n;i++)

		expend(s[i]-'a');

	int ans=0;

	scanf("%s",s);

	n=strlen(s);

	for (int i=0,now=1,len=0;i<n;i++){

		int c=s[i]-'a';

		if (t[now].Next[c]){

			now=t[now].Next[c];

			ans=max(ans,++len);

			continue;

		}

		while (!t[now].Next[c])

			now=t[now].fa;

		ans=max(ans,len=t[now].Max+1);

		now=t[now].Next[c];

	}

	printf("%d",ans);

	return 0;

}

巴特西

SPOJ LCS - Longest Common Substring 字符串 SAM

题目传送门 - SPOJ LCS

题意

题解

代码

最新文章

热门文章