BZOJ 4698: Sdoi2008 Sandy的卡片

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
//by NeighThorn
using namespace std;

const int maxn=1000+5,maxm=1000+5,maxlen=2000000+5;

int n,m,Min,s[maxlen],id[maxlen],len[maxn],vis[maxn],str[maxn][maxm];
int sa[maxlen],gs[maxlen],wb[maxlen],wv[maxlen],ran[maxlen],height[maxlen];

inline bool cmp(int *x,int a,int b,int l){
	return x[a]==x[b]&&x[a+l]==x[b+l];
}

inline void da(int *sa,int *x,int n,int m){
	int i,j,p,*y=wb;
	for(i=0;i<m;i++) gs[i]=0;
	for(i=0;i<n;i++) gs[x[i]]++;
	for(i=1;i<m;i++) gs[i]+=gs[i-1];
	for(i=n-1;~i;i--) sa[--gs[x[i]]]=i;
	for(j=1,p=1;p<n;j<<=1,m=p){
		for(i=n-j,p=0;i<n;i++) y[p++]=i;
		for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
		for(i=0;i<n;i++) wv[i]=x[y[i]];
		for(i=0;i<m;i++) gs[i]=0;
		for(i=0;i<n;i++) gs[wv[i]]++;
		for(i=1;i<m;i++) gs[i]+=gs[i-1];
		for(i=n-1;~i;i--) sa[--gs[wv[i]]]=y[i];
		p=1;swap(x,y);x[sa[0]]=0;
		for(i=1;i<n;i++) x[sa[i]]=cmp(y,sa[i],sa[i-1],j)?p-1:p++;
	}
}

inline void calcheight(int n){
	int i,j,k=0;
	for(i=0;i<=n;i++) ran[sa[i]]=i;
	for(i=0;i<n;height[ran[i++]]=k)
		for(k?k--:233,j=sa[ran[i]-1];s[j+k]==s[i+k];k++);
}

inline bool check(int k){
	int cnt=0;
	for(int l=1,r;l<=n;l=r+1){
		while(l<n&&height[l]<k) l++;
		r=l;if(r==n&&height[r]<k) return false;
		while(r<n&&height[r+1]>=k) r++;
		if(r-l+2>=m){
			memset(vis,0,sizeof(vis));cnt=0;
			for(int i=l-1;i<=r;i++)
				if(id[sa[i]]) cnt+=vis[id[sa[i]]]^1,vis[id[sa[i]]]=1;	
			if(cnt==m) return true;
		}
	}
	return false;
}

signed main(void){
#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
#endif
	scanf("%d",&m);Min=1000;
	for(int i=1;i<=m;i++){
		scanf("%d",&len[i]),Min=min(Min,len[i]);
		for(int j=1;j<=len[i];j++)
			scanf("%d",&str[i][j]);
	}
	n=0;
	for(int i=1;i<=m;i++,ran[n]=s[n++]=2000+i)
		for(int j=2;j<=len[i];j++)
			id[n]=i,ran[n]=s[n++]=str[i][j]-str[i][j-1];
	da(sa,ran,n+1,4000);calcheight(n);
	int l=1,r=Min-1,ans=0;
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid)) ans=mid,l=mid+1;
		else r=mid-1;
	}
	printf("%d\n",ans+1);
	return 0;
}