自动搬运

查看原文

来自洛谷，原作者为

	xMinh **

搬运于2025-08-24 21:37:58，当前版本为作者最后更新于2018-03-26 09:24:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

抵制mhr(@明月の卫——AH)暴力题解 从我做起！

SA多好啊

本题有多种解法 但是本蒟蒻只会后缀数组

关于后缀数组的详细讲解：

蒟蒻的博客

我们先把所有串连接在一起，用后缀数组求出LCP，然后二分长度，每次从头到尾扫一遍。

但是要注意连接的时候要加分割标记，这个只需要往两个串中间放一个大数就可以了。

根据LCP Theorem(证明过程见我博客)

LCP(i,k)=min(LCP(j,j-1)) 对于任意1<i<=j<=k<=n

设height[i]=LCP(i,i-1)

只要有n个>=len的height且其首字母属于不同的串就可以了

上代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
#define Big (1000000000 + 10)
#define maxn 111111
using namespace std;
int sa[maxn],rk[maxn],b[maxn],c[maxn],x[maxn],y[maxn];
int height[maxn],stack[maxn],id[maxn],len[1010],a[1010][1010];
int num,cnt,n,m,l,r,maxx,minn,ans,top;
bool vis[maxn]; 

int read() {
	char c=getchar();
	int r=0,f=1;
	while (!isdigit(c)) {
		if (c=='-') f=-1;
		c=getchar();
	}
	while (isdigit(c)) {
		r=(r*10)+(c^48);
		c=getchar();
	}
	return r*f;
}

int min(int x,int y) {return x<y?x:y;}
int max(int x,int y) {return x>y?x:y;}

void Get_SA() {
	for (int i=1;i<=n;i++) ++c[x[i]=b[i]];
	for (int i=2;i<=m;i++) c[i]+=c[i-1];
	for (int i=n;i>=1;i--) sa[c[x[i]]--]=i;
	
	for (int k=1;k<=n;k<<=1) {
		cnt=0;
		for (int i=n-k+1;i<=n;i++) y[++cnt]=i;
		for (int i=1;i<=n;i++) if (sa[i]>k) y[++cnt]=sa[i]-k;
		
		for (int i=1;i<=m;i++) c[i]=0;
		for (int i=1;i<=n;i++) ++c[x[i]];
		for (int i=2;i<=m;i++) c[i]+=c[i-1];
		for (int i=n;i>=1;i--) sa[c[x[y[i]]]--]=y[i],y[i]=0;
		
		swap(x,y);
		x[sa[1]]=1; cnt=1;
		for (int i=2;i<=n;i++) 
			x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k])?cnt:++cnt;
		if (cnt==n) break;
		m=cnt;
	}
}

void Get_Height() {
	int k=0;
	for (int i=1;i<=n;i++) rk[sa[i]]=i;
	for (int i=1;i<=n;i++) {
		if (rk[i]==1) continue;
		if (k) --k;
		int j=sa[rk[i]-1];
		while (j+k<=n && i+k<=n && b[i+k]==b[j+k]) ++k;
		height[rk[i]]=k;
	}
}

bool check(int x) {
	while (top) vis[stack[top--]]=0;
	for (int i=1;i<=n;i++) {
		if (height[i]<x) {
			while (top) vis[stack[top--]]=0;
		}
		if (!vis[id[sa[i]]]) {
			vis[id[sa[i]]]=1;
			stack[++top]=id[sa[i]];
			if (top==num) return 1; 
		}
	}
	return 0;
}

int main() {
	num=read(); 
	l=0;r=minn=Big;
	for (int i=1;i<=num;i++) {
		len[i]=read();
		for (int j=1;j<=len[i];j++) {
			a[i][j]=read();
			if (j!=1) maxx=max(maxx,a[i][j]-a[i][j-1]);
		}
		r=min(r,len[i]-1);
	}
	for (int i=1;i<=num;i++) {
		for (int j=2;j<=len[i];j++) {
			b[++n]=a[i][j]-a[i][j-1];
			id[n]=i;
			minn=min(minn,b[n]);
		}
		b[++n]=++maxx;
	}
	for (int i=1;i<=n;i++) {
		b[i]=b[i]-minn+1;
		m=max(m,b[i]);
	}
	Get_SA();
	Get_Height();
	while (l<=r) {
		int mid=(l+r)>>1;
		if (check(mid)) {
			l=mid+1;
			ans=mid;
		}
		else r=mid-1;
	}
	printf("%d",ans+1);
}