题目描述

Description

Sandy和Sue的热衷于收集干脆面中的卡片。然而，Sue收集卡片是因为卡片上漂亮的人物形象，而Sandy则是为了积
攒卡片兑换超炫的人物模型。每一张卡片都由一些数字进行标记，第i张卡片的序列长度为Mi，要想兑换人物模型
，首先必须要集够N张卡片，对于这N张卡片，如果他们都有一个相同的子串长度为k，则可以兑换一个等级为k的人
物模型。相同的定义为：两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串。Sandy的卡片数远
远小于要求的N，于是Sue决定在Sandy的生日将自己的卡片送给Sandy，在Sue的帮助下，Sandy终于集够了N张卡片
，但是，Sandy并不清楚他可以兑换到哪个等级的人物模型，现在，请你帮助Sandy和Sue，看看他们最高能够得到
哪个等级的人物模型。

Input

第一行为一个数N，表示可以兑换人物模型最少需要的卡片数，即Sandy现在有的卡片数
第i+1行到第i+N行每行第一个数为第i张卡片序列的长度Mi，之后j+1到j+1+Mi个数，用空格分隔，分别表示序列中
的第j个数
n<=1000,M<=1000,2<=Mi<=101

Output

一个数k，表示可以获得的最高等级。

Sample Input

2
2 1 2
3 4 5 9

Sample Output

2

题目分析

差分原序列后进行hash即可

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
int n;
int str[1010][110];
int len[1100];
int seed=26,p=1000000009;
long long po[2010];
void init()
{
    po[0]=1;
    for(int i=1;i<=2000;i++) po[i]=po[i-1]*seed%p;
}
int minn=0x7f7f7f7f,ans=1;
map<int,int> m[1010];
int check(int mid)
{
    for(int i=1;i<=n;i++) m[i].clear();
    long long tmp=0;
    for(int i=1;i<n;i++)
    {
        tmp=0;
        for(int j=1;j<=mid;j++)
            tmp=(tmp*seed+str[i][j])%p;
        for(int j=mid;j<=len[i];j++)
            m[i][tmp]=1,tmp=(((tmp-po[mid-1]*(str[i][j+1-mid])%p+p)%p)*seed+(str[i][j+1]))%p;
    }
    tmp=0;
    int fla=0;
    for(int i=1;i<=mid;i++) tmp=(tmp*seed+str[n][i])%p;
    for(int i=mid;i<=len[n];i++)
    {
        int flag=1;
        for(int j=1;j<n;j++) if(m[j][tmp]==0) flag=0;
        if(flag) 
        {
            fla=1;
            if(i==1&&mid==1) ans=max(ans,1);
            else ans=max(ans,mid+1);
        }
        tmp=(((tmp-po[mid-1]*(str[n][i+1-mid])%p+p)%p)*seed+(str[n][i+1]))%p;
    }
    if(fla) return 1;
    return 0;
}
int main()
{
    scanf("%d",&n);
    init();
    for(int tmp,i=1;i<=n;i++)
    {
        scanf("%d",&tmp);
        for(int j=1;j<=tmp;j++) scanf("%d",&str[i][j]);
        for(int j=tmp;j>=2;j--) str[i][j]=str[i][j]-str[i][j-1];
        minn=min(minn,tmp),len[i]=tmp;
    }
    int l=0,r=minn,mid;
    while(l<r)
    {
        mid=(l+r)>>1;
        if(check(mid)) l=mid+1;
        else r=mid;
    }
    printf("%d",ans);
    return 0;
}