题目链接

传送门

题目大意

有 n 张卡片，每张卡片上有一个序列，求这些序列最长相同子串的长度。两个子串相同定义为两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串。

问题转化

为了处理题目中定义的“相同”子串，我们先把这 n 个序列做个差分，得到第 i 个元素与第 i-1 个元素的差。这样，若这些序列的最长公共子串的长度为 len ，则题目中定义的最长相同子串的长度为 len+1 。于是，我们就完成了将问题模型变成求多个序列的最长公共子串的转化。

算法分析

本题的做法很多，这里介绍后缀数组的解法。

• 我们把差分后的序列顺次拼接起来，用一个大数作为间隔符连接；

• 先用倍增的方法对后缀进行排序，求出 sa 数组和 rank 数组；

• 再求出 height 数组，height[i] 表示排名第 i 的后缀与排名第 i-1 的后缀的最长公共前缀（LCP）长度；

• 二分答案 len 检验长度为 len 的相同子串（即差分后长度为 len-1 的公共子串）是否存在；

• 根据 LCP的相关定理 ，我们知道对于任意一对 i, j(rank[i]<rank[j]) ，后缀 i 与后缀 j 的 LCP 长度为 \underset{ rank[i]<k \leq rank[j] }{ min } \; height[k] 。 我们在串中找出所有极大子区间 [l, r] ， 使得对于所有 k(l \leq k \leq r) 都有 height[k] \geqslant len-1 ，若 sa[l-1]...sa[r] 分别属于 n 个序列，则说明有解；

• 找到上述子区间的方法：使用两个指针 i, j ， 如果 height[j] \geqslant len-1 则 j++ ，否则 [i, j] 即为所求区间，检验答案并 i=++j 。

代码实现

#include <cstdio>
#include <cstring>
const int MAXN=1100000;
const int MAXM=1100;
const int BASE=1000;
const int MAXS=BASE*2+5;
int n, m;
int a[MAXN], b[MAXN];
int st[MAXS];
int sa[MAXN];
int rank[MAXN*2];
int rank1[MAXN];
int tmp[MAXN];
int count[MAXN];
int height[MAXN];
bool used[MAXM];
bool check(int len)
{
    memset(used, 0, sizeof used);
    for (int i=2, j=1, c=0; j<=n; j++)
    {
        if (!used[b[sa[j]]]) used[b[sa[j]]]=1, c++;
        if (height[j+1]<len-1)
        {
            if (c==m) return 1;
            for (int k=i-1; k<=j; k++)
                if (used[b[sa[k]]]) used[b[sa[k]]]=0, c--;
            i=j+1;
        }
    }
    return 0;
}
int main()
{
//  freopen("bzoj4698.in", "r", stdin);
//  freopen("bzoj4698.out", "w", stdout);
    scanf("%d", &m);
    for (int i=1, k, t; i<=m; i++)
    {
        scanf("%d%d", &k, &t);
        for (int j=1, x; j<k; j++)
            scanf("%d", &x), a[++n]=x-t+BASE, b[n]=i, t=x;
        a[++n]=MAXS-1;
    }
    for (int i=1; i<=n; i++) st[a[i]]++;
    for (int i=1; i<MAXS; i++) st[i]+=st[i-1];
    for (int i=1; i<=n; i++) rank[i]=st[a[i]];
    for (int p=1, k=0; k!=n; p<<=1)
    {
        memset(count, 0, sizeof count);
        for (int i=1; i<=n; i++) count[rank[i+p]]++;
        for (int i=1; i<=n; i++) count[i]+=count[i-1];
        for (int i=n; i>=1; i--) tmp[count[rank[i+p]]--]=i;
        memset(count, 0, sizeof count);
        for (int i=1; i<=n; i++) count[rank[i]]++;
        for (int i=1; i<=n; i++) count[i]+=count[i-1];
        for (int i=n; i>=1; i--) sa[count[rank[tmp[i]]]--]=tmp[i];
        memcpy(rank1, rank, sizeof rank1);
        rank[sa[1]]=k=1;
        for (int i=2; i<=n; i++)
        {
            if (rank1[sa[i]]!=rank1[sa[i-1]]||rank1[sa[i]+p]!=rank1[sa[i-1]+p]) k++;
            rank[sa[i]]=k;
        }
    }
    for (int i=1, k=0; i<=n; i++)
    {
        if (rank[i]==1) { height[1]=k=0; continue; }
        if (--k<0) k=0;
        while (a[i+k]==a[sa[rank[i]-1]+k]) k++;
        height[rank[i]]=k;
    }
    int l=1, r=100;
    while (l<r)
    {
        int mid=(l+r+1)/2;
        if (check(mid)) l=mid;
        else r=mid-1;
    }
    printf("%d\n", l);
    return 0;
}