【SPOJ】Longest Common Substring II

多个字符串求最长公共子串

还是将一个子串建SAM，其他字符串全部跑一边，记录每个点的最大贡献

由于是所有串，要对每个点每个字符串跑完后去最小值才是每个点的最终贡献

#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=200000;

LL nod,last,n,T;

LL len[maxn],fail[maxn],son[maxn][26],Ans[maxn],sum[maxn],c[maxn],p[maxn];

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');

	for(LL i=1;i<=nod;++i)

	    c[len[i]]++;

    for(int i=1;i<=nod;++i)

	    c[i]+=c[i-1];

    for(int i=1;i<=nod;++i)

	    p[c[len[i]]--]=i;

    for(int i=1;i<=nod;++i)

	    Ans[i]=len[i];

	while(scanf("%s",s)!=EOF){

		memset(sum,0,sizeof(sum));

		LL 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];

		    }

	        sum[now]=max(sum[now],cnt);

	    }

	    for(LL i=nod;i>=1;--i)

	        sum[fail[p[i]]]=max(sum[fail[p[i]]],sum[p[i]]);

        for(int i=1;i<=nod;++i)

		    Ans[i]=min(Ans[i],sum[i]);

	}

	LL ans=0;

	for(LL i=1;i<=nod;++i)

	    ans=max(ans,Ans[i]);

	printf("%lld",ans);

	return 0;

}/*

fjewiofejhiofjmwopejeugfzjkjnfoakweldnfmoierhguiewkjfkowejrfoiwejsfd

jwierhdwuiek,dedjfkz[pjeowrfhuqigrfwerljfiuekdfkcdfheosf

*/

秒客网

【SPOJ】Longest Common Substring II

相关文章