1 条题解
-
0
#include<bits/stdc++.h> using namespace std; const int N=1005; int n,m,k,s,t; int a[N][105],nex[105],b[105]; int main(){ freopen("in.txt","r",stdin); cin>>n; for (int i=1;i<=n;++i){ cin>>a[i][0]; cin>>s; for (int j=1;j<a[i][0];++j){ cin>>t; a[i][j]=t-s;//求差分 s=t; } } int ans=0; for (int k=1;k<a[1][0];++k){//枚举第一张卡片的起始位置 int l=a[1][0]-k; for (int i=1;i<=l;++i) b[i]=a[1][k+i-1]; nex[1]=0; for (int i=2,j=0;i<=l;++i){//求该起始位置的nex数组 while (j && b[i]!=b[j+1]) j=nex[j]; if (b[i]==b[j+1]) ++j; nex[i]=j; } int tmp=0x3f3f3f3f; for (int p=2;p<=n;++p){ int x=0; for (int i=1,j=0;i<a[p][0];++i){//kmp匹配 while (j>0 && (j==l || a[p][i]!=b[j+1])) j=nex[j]; if (a[p][i]==b[j+1]) ++j; x=max(x,j);//字符串中找最大能匹配的长度 } tmp=min(tmp,x);//所有字符串的最大匹配中找最小的 } ans=max(ans,tmp);//所有起始位置中找最大的 } cout<<ans+1; }
- 1
信息
- ID
- 278
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 6
- 标签
- 递交数
- 62
- 已通过
- 20
- 上传者