【SPOJ】Longest Common Substring

求两个字符串的最长公共子串

对一个串建好后缀自动机然后暴力跑一下废话

讲一下怎么跑吧

从第一个字符开始遍历，遍历不到了再沿着\(parents\)走看能否找到出路，走到某个点时，统计一下走过了多少点然后更新答案

来说说这样做的正确性：

遍历是肯定的， SAM 从根节点出发的任意路径都表示一个子串

沿着\(parents\)边往后走，保证贪心情况下维护最长公共子串寻找出路

注意这里是统计走过了多少点更新答案，不能直接通过\(len\)更新答案

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

typedef long long LL;

const LL maxn=600000;

LL nod,last,n,T;

LL len[maxn],fail[maxn],son[maxn][26];

char s[maxn];

inline void Insert(LL c){

	LL np=++nod,p=last;

	len[np]=len[p]+1;

	last=np;

	while(p&&!son[p][c]){

		son[p][c]=np,

		p=fail[p];

	}

	if(!p)

	    fail[np]=1;

	else{

		LL q=son[p][c];

		if(len[q]==len[p]+1)

		    fail[np]=q;

		else{

			LL nq=++nod;

			len[nq]=len[p]+1;

			fail[nq]=fail[q];

			memcpy(son[nq],son[q],sizeof(son[q]));

			fail[np]=fail[q]=nq;

			while(p&&son[p][c]==q){

				son[p][c]=nq,

				p=fail[p];

			}

		}

	}

}

int main(){

	nod=last=1;

	scanf(" %s",s);

	LL Len=strlen(s);

	for(LL i=0;i<Len;++i)

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

	scanf(" %s",s);

	LL ans=0,now=1,cnt=0;

	Len=strlen(s);

	for(LL i=0;i<Len;++i){

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

		if(son[now][c])

		    ++cnt,

		    now=son[now][c];

		else{

			while(now&&!son[now][c])

			    now=fail[now];

			if(!now)

				cnt=0,

			    now=1;

			else

			    cnt=len[now]+1,

			    now=son[now][c];

		}

	    ans=max(ans,cnt);

	}

	printf("%lld\n",ans);

	return 0;

}/*

fjewiofejhiofjmwopejeugfzjkjnfoakweldnfmoierhguiewkjfkowejrfoiwejsfd

jwierhdwuiek,dedjfkz[pjeowrfhuqigrfwerljfiuekdfkcdfheosf

*/

巴特西

【SPOJ】Longest Common Substring

最新文章

热门文章