1 条题解

  • 0
    @ 2023-7-10 17:14:04

    image

    #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
    上传者