Luogu

BZOJ

分析

后缀数组。

首先加上一个数不太好处理,但是加之后差不变,所以可以把差分之后的串拿出来。

那么问题就变成,给出一些串,求它们的最长公共子串。

先按照套路把这些串拼在一起,中间拿没出现过的不相同的数作分隔。

考虑二分答案。把 $height$ 大于 $mid$ 的后缀分成一组,然后如果有一组达到了 $n$ 个就可行。

具体实现及细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;
const int C=2000;

int T,n=0;
int a[N],s[N],bl[N];

int sa[N],rnk[N],height[N];
int x[N],y[N],z[N];

inline void Suffix_Sort() {
    int m=10000;
    for (re int i=1;i<=n;++i) ++z[x[i]=s[i]];
    for (re int i=2;i<=m;++i) z[i]+=z[i-1];
    for (re int i=n;i>=1;--i) sa[z[x[i]]--]=i;
    for (re int k=1;k<=n;k<<=1) {
        int p=0;
        for (re int i=n-k+1;i<=n;++i) y[++p]=i;
        for (re int i=1;i<=n;++i) if (sa[i]>k) y[++p]=sa[i]-k;
        for (re int i=1;i<=m;++i) z[i]=0;
        for (re int i=1;i<=n;++i) ++z[x[i]];
        for (re int i=2;i<=m;++i) z[i]+=z[i-1];
        for (re int i=n;i>=1;--i) sa[z[x[y[i]]]--]=y[i],y[i]=0;
        swap(x,y),x[sa[1]]=1,p=1;
        for (re int i=2;i<=n;++i)
            x[sa[i]]=(y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k])?p:++p;
        if (p==n) break; m=p;
    }
}

inline void Get_Height() {
    for (re int i=1;i<=n;++i) rnk[sa[i]]=i;
    for (re int i=1,j=0;i<=n;++i) {
        if (j) --j; int p=sa[rnk[i]-1];
        while (s[i+j]==s[p+j]) { ++j; }
        height[rnk[i]]=j;
    }
}


inline int check(int mid) {
    static int tot=0,c[N]; ++tot;
    for (re int i=1,cnt=0;i<=n;++i) {
        if (height[i]<mid) ++tot,cnt=0;
        if (c[bl[sa[i]]]!=tot) c[bl[sa[i]]]=tot,++cnt;
        if (cnt==T) return 1;
    }
    return 0;
}

int main() {
    T=read();
    for (re int i=1;i<=T;++i) {
        int m=read();
        for (re int j=1;j<=m;++j) a[j]=read();
        for (re int j=1;j<m;++j) a[j]=a[j+1]-a[j]+C;
        for (re int j=1;j<m;++j) s[++n]=a[j],bl[n]=i;
        s[++n]=i+C*4;
    }
    Suffix_Sort(); Get_Height();
    int L=0,R=n;
    while (L<R) {
        int mid=(L+R+1)>>1;
        if (check(mid)) L=mid;
        else R=mid-1;
    }
    printf("%d\n",L+1);
    return 0;
}
最后修改:2019 年 09 月 25 日 01 : 36 PM