「BZOJ2946」[POI2000] 公共串

2015年4月21日5,3801

Description

给出几个由小写字母构成的单词，求它们最长的公共子串的长度。

任务：

l 读入单词

l 计算最长公共子串的长度

l 输出结果

Input

文件的第一行是整数 n，1<=n<=5，表示单词的数量。接下来n行每行一个单词，只由小写字母组成，单词的长度至少为1，最大为2000。

Output

仅一行，一个整数，最长公共子串的长度。

Sample Input

3
abcb
bca
acbc

Sample Output

２

题解

~~后缀自动机没学清楚叫你装叉，看hzwer这个傻逼wa了多少发。。。~~

第一个串建自动机，每个串放进去匹配，得出每个状态的最大匹配长度

每个状态取所有串最小值，得出最大公共子串长

对所有状态子串长取最大值就是答案

~~叫你装叉不写哈希~~

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define mod 1000000007
#define pa pair<int,int>
#define ll long long 
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n;
char ch[2005];
struct sam{
	int cnt,last;
	int fa[4005],a[4005][27],mx[4005],len[4005],ans[4005];
	int v[4005],q[4005];
	sam(){
		last=++cnt;
	}
	void extend(int c){
		int p=last,np=last=++cnt;mx[np]=mx[p]+1;
		while(!a[p][c]&&p)a[p][c]=np,p=fa[p];
		if(!p)fa[np]=1;
		else 
		{
			int q=a[p][c];
			if(mx[p]+1==mx[q])fa[np]=q;
			else 
			{
				int nq=++cnt;mx[nq]=mx[p]+1;
				memcpy(a[nq],a[q],sizeof(a[q]));
				fa[nq]=fa[q];
				fa[np]=fa[q]=nq;
				while(a[p][c]==q)a[p][c]=nq,p=fa[p];
			}
		}
	}
	void pre(){
		for(int i=1;i<=cnt;i++)ans[i]=mx[i];
		for(int i=1;i<=cnt;i++)v[mx[i]]++;
		for(int i=1;i<=cnt;i++)v[i]+=v[i-1];
		for(int i=cnt;i;i--)q[v[mx[i]]--]=i;
	}
	void solve(){
		scanf("%s",ch+1);
		memset(len,0,sizeof(len));
		int l=strlen(ch+1),p=1,tmp=0;
		for(int i=1;i<=l;i++)
		{
			int c=ch[i]-'a';
			while(!a[p][c]&&p)p=fa[p];
			if(p==0)p=1,tmp=0;
			else tmp=min(tmp,mx[p])+1,p=a[p][c];
			len[p]=max(len[p],tmp);
		}
		for(int i=cnt;i;i--)len[fa[q[i]]]=max(len[fa[q[i]]],len[q[i]]);
		for(int i=1;i<=cnt;i++)ans[i]=min(ans[i],len[i]);
	}
}sam;
int main()
{
	n=read();
	scanf("%s",ch+1);
	int l=strlen(ch+1);
	for(int i=1;i<=l;i++)sam.extend(ch[i]-'a');
	sam.pre();
	for(int i=1;i<n;i++)sam.solve();
	int ans=0;
	for(int i=1;i<=sam.cnt;i++)
		ans=max(ans,sam.ans[i]);
	printf("%d\n",ans);
	return 0;
}

#include<set>

#include<map>

#include<ctime>

#include<queue>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define mod 1000000007

#define pa pair<int,int>

#define ll long long

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n;

char ch[2005];

struct sam{

int cnt,last;

int fa[4005],a[4005][27],mx[4005],len[4005],ans[4005];

int v[4005],q[4005];

sam(){

last=++cnt;

}

void extend(int c){

int p=last,np=last=++cnt;mx[np]=mx[p]+1;

while(!a[p][c]&&p)a[p][c]=np,p=fa[p];

if(!p)fa[np]=1;

else

{

int q=a[p][c];

if(mx[p]+1==mx[q])fa[np]=q;

else

{

int nq=++cnt;mx[nq]=mx[p]+1;

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

fa[nq]=fa[q];

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

while(a[p][c]==q)a[p][c]=nq,p=fa[p];

}

void pre(){

for(int i=1;i<=cnt;i++)ans[i]=mx[i];

for(int i=1;i<=cnt;i++)v[mx[i]]++;

for(int i=1;i<=cnt;i++)v[i]+=v[i-1];

for(int i=cnt;i;i--)q[v[mx[i]]--]=i;

}

void solve(){

scanf("%s",ch+1);

memset(len,0,sizeof(len));

int l=strlen(ch+1),p=1,tmp=0;

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

{

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

while(!a[p][c]&&p)p=fa[p];

if(p==0)p=1,tmp=0;

else tmp=min(tmp,mx[p])+1,p=a[p][c];

len[p]=max(len[p],tmp);

}

for(int i=cnt;i;i--)len[fa[q[i]]]=max(len[fa[q[i]]],len[q[i]]);

for(int i=1;i<=cnt;i++)ans[i]=min(ans[i],len[i]);

}

}sam;

int main()

{

n=read();

scanf("%s",ch+1);

int l=strlen(ch+1);

for(int i=1;i<=l;i++)sam.extend(ch[i]-'a');

sam.pre();

for(int i=1;i<n;i++)sam.solve();

int ans=0;

for(int i=1;i<=sam.cnt;i++)

ans=max(ans,sam.ans[i]);

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

return 0;

}

« 「POJ1743」Musical Theme 「BZOJ3998」[TJOI2015] 弦论 »

ez_zjt

扑通扑通跪下来

hzwer.com _ Home | http://hzwer.com

「BZOJ2946」[POI2000] 公共串

Description

Input

Output

Sample Input

Sample Output

题解

分类目录

热门文章

Myfriends

近期评论