差分,枚举一个串的所有后缀,暴力在所有其他串中kmp,复杂度$O(nm^2)$。
#include<cstdio>
const int N=1005;
const int M=105;
int n,m,t[N][M],f[M];
void eq1(int&a,int b){a=b<a?b:a;}
void eq2(int&a,int b){a=a<b?b:a;}
void pre(int*t){
int i=0,j=f[0]=-1;
while(t[i]){
while(~j&&t[i]^t[j])j=f[j];
f[++i]=++j;
}
}
int sol(int*s,int*t){
int i=0,j=0,k=0;
while(s[i]){
while(~j&&s[i]^t[j])j=f[j];
++i,eq2(k,++j);
}
return k;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
int*s=t[i];
scanf("%d",&m),--m;
for(int j=0;j<=m;++j)
scanf("%d",s+j);
for(int j=m;j;--j)
s[j]=s[j]-s[j-1]+1e9;
}
int e=0;
for(int j=1;j<=m;++j){
pre(t[n]+j);
int v=m-j+1;
for(int i=1;i<n;++i)
eq1(v,sol(t[i]+1,t[n]+j));
eq2(e,v);
}
printf("%d\n",e+1);
}