题目地址：洛谷：【P2463】[SDOI2008]Sandy的卡片 – 洛谷、BZOJ：Problem 4698. — Sdoi2008 Sandy的卡片

题目描述

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

输入输出格式

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

输出格式：
一个数k，表示可以获得的最高等级。

输入输出样例

输入样例#1：

2
2 1 2
3 4 5 9

输出样例#1：

2

说明

数据范围：
30%的数据保证n<=50
100%的数据保证n<=1000,M<=1000,2<=Mi<=101

题解

找最长公共子串啊，DP？显然不是DP，那是两个字符串。
我们考虑用字符串匹配算法来做，选定第一个串为模式串，来匹配剩下的串。
加上一个数变成另一个串怎么做？差分掉。
子串怎么做？枚举子串，分别匹配。
等一下，现在的算法好像是O(len^2 \cdot \sum len)的耶，好像不太可做。
我们只枚举子串的起点，然后在KMP过程中记录下最长匹配长度即可。
最后的时间复杂度是O(len \cdot \sum len)，好像可做。

代码

// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>

#include <algorithm>
#include <vector>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 1005, INF = 1e9;

int n, t, fail[MAXN], ans;
std::vector<int> str[MAXN];

inline void calfail(int x) {
    memset(fail, 0, sizeof(fail));
    int i = 0, j = -1;
    fail[0] = -1;
    for(; i < str[x].size(); i++, j++) {
        while(j >= 0 && str[x][j] != str[x][i]) {
            j = fail[j];
        }
        fail[i + 1] = str[x][j + 1] == str[x][i + 1] ? fail[j + 1] : j + 1;
    }
}

inline int match(int t, int p) {
    int i = 0, j = 0, cnt = -INF;
    for(; i < str[t].size(); i++, j++) {
        while(j >= 0 && str[p][j] != str[t][i]) {
            j = fail[j];
        }
        cnt = std::max(cnt, j);
    }
    return cnt + 2;
}

int main() {
    n = readint();
    for(int i = 0; i < n; i++) {
        t = readint();
        for(int j = 0; j < t; j++) {
            str[i].push_back(readint());
        }
        for(int j = 0; j < t - 1; j++) {
            str[i][j] = str[i][j + 1] - str[i][j];
        }
        str[i].pop_back();
    }
    for(int i = 0; !str[0].empty(); i++) {
        calfail(0);
        int tmp = INF;
        for(int j = 1; j < n; j++) {
            tmp = std::min(tmp, match(j, 0));
        }
        str[0].erase(str[0].begin());
        ans = std::max(ans, tmp);
    }
    printf("%d", ans);
    return 0;
}