bzoj 2946: [Poi2000]公共串 — 后缀自动机

2946: [Poi2000]公共串

Time Limit: 3 Sec  Memory Limit: 128 MB

Description

Input

Output

Sample Input

Sample Output

HINT

Source

基本上就是SAM的模板题吧

关于SAM  kylelv.com/?p=459

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define inf 1000000007
#define ll long long
#define N 4010
int n,m;
char s[N];
int fa[N],ch[N][26],l[N],cnt,lst;
void ins(int x)
{
	int p,q,np,nq;
	p=lst;lst=np=++cnt;l[np]=l[p]+1;
	while(!ch[p][x]&&p) ch[p][x]=np,p=fa[p];
	if(!p){fa[np]=1;return;}
	q=ch[p][x];
	if(l[q]==l[p]+1){fa[np]=q;return;}
	nq=++cnt;l[nq]=l[p]+1;
	memcpy(ch[nq],ch[q],sizeof(ch[q]));
	fa[nq]=fa[q];
	fa[q]=fa[np]=nq;
	while(ch[p][x]==q&&p) ch[p][x]=nq,p=fa[p];
}
int q[N],v[N],ans[N],mx[N];
void pre()
{
	for(int i=1;i<=cnt;i++) v[l[i]]++;
	for(int i=1;i<=n;i++) v[i]+=v[i-1];
	for(int i=cnt;i;i--) q[v[l[i]]--]=i;
	for(int i=1;i<=cnt;i++) ans[i]=l[i];
}
void sol()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	memset(mx,0,sizeof(mx));
	int p,now=1,len=0,x;
	for(int i=1;i<=n;i++)
	{
		x=s[i]-'a';
		while(!ch[now][x]&&now) now=fa[now];
		if(!now) now=1,len=0;
		else len=min(len,l[now])+1,now=ch[now][x];
		mx[now]=max(mx[now],len);
	}
	for(int i=cnt;i;i--) mx[fa[q[i]]]=max(mx[fa[q[i]]],mx[q[i]]);
	for(int i=1;i<=cnt;i++) ans[i]=min(ans[i],mx[i]);
}
int Ans; 
int main()
{
	scanf("%d",&m);
	scanf("%s",s+1);
	lst=cnt=1;
	n=strlen(s+1);
	for(int i=1;i<=n;i++) ins(s[i]-'a');
	pre();
	for(int i=2;i<=m;i++) sol();
	for(int i=1;i<=cnt;i++) Ans=max(Ans,ans[i]);
	printf("%d\n",Ans);
	return 0;
}