[BZOJ4698][Sdoi2008]Sandy的卡片

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;

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

#define maxn 1010
#define maxl 110

int n, len[maxn], S[maxn][maxl], Fail[maxl];

int main() {
	n = read();
	for(int i = 1; i <= n; i++) {
		len[i] = read();
		for(int j = 1; j <= len[i]; j++) S[i][j] = read();
		len[i]--;
		for(int j = 1; j <= len[i]; j++) S[i][j] = S[i][j+1] - S[i][j];
	}
	/*for(int i = 1; i <= n; i++)
		for(int j = 1; j <= len[i]; j++) printf("%d%c", S[i][j], j < len[i] ? ‘ ‘ : ‘\n‘); // */
	
	int ans = 0;
	for(int st = 1; st <= len[1] - ans; st++) {
		int nl = len[1] - st + 1;
		for(int i = 2; i <= nl + 1; i++) {
			int j = Fail[i-1];
			while(j > 1 && S[1][j+st-1] != S[1][i+st-2]) j = Fail[j];
			Fail[i] = S[1][j+st-1] == S[1][i+st-2] ? j + 1 : 1;
		}
		int p, k = len[1];
		for(int x = 2; x <= n; x++) {
			p = 1; int tmp = 0;
			for(int i = 1; i <= len[x]; i++) {
				while(p > 1 && S[1][p+st-1] != S[x][i]) p = Fail[p];
				p = S[1][p+st-1] == S[x][i] ? p + 1 : 1;
				tmp = max(tmp, p - 1);
			}
			k = min(k, tmp);
			if(k <= ans) break;
		}
		ans = max(ans, k);
	}
	
	printf("%d\n", ans + 1);
	
	return 0;
}