后缀数组之多串公共子串长度

﹏ヽ暗。殇╰゛Y 2024-04-17 19:55 73阅读 0赞

码力很差 但是还是写出来了，用时 一个小时40分钟。有点激动

写个博客记录一下~

果然越枯燥越写不出来，和同学边聊天边写，还是有效率，lf同学真是幸运星，哈哈哈哈，

题目：

### 题目描述 ###

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**复制

### 说明/提示 ###

数据范围：

30%的数据保证n<=50

100%的数据保证n<=1000,M<=1000,2<=Mi<=101

update：题面上数据范围mi和m的范围其实是一个东西... 真实数据范围:40<=n<=1000,2<=mi<=101,字符串中的每个数字的大小范围为\[0,1864\]

AC代码：

#include<bits/stdc++.h>
    using namespace std;
    const int M=1e6+1100;
    int f[1010],n,a[1010][1010],cnt,b[M],loc[M];
    struct Node{
        int n,m,rk[M],height[M],c[M],sa[M],x[M],y[M],d[M];
        void getsa(){
            for(int i=0;i<=m;i++) c[i]=0;
            for (int i=1; i<=n; ++i) ++c[x[i]=d[i]];
            for (int i=2; i<=m; ++i) c[i]+=c[i-1];
            for (int i=n; i>=1; --i) sa[c[x[i]]--]=i;
            for (int k=1; k<=n; k<<=1) {
                int num=0;
                for (int i=n-k+1; i<=n; ++i) y[++num]=i;
                for (int i=1; i<=n; ++i) if (sa[i]>k) y[++num]=sa[i]-k;
                for (int i=1; i<=m; ++i) c[i]=0;
                for (int i=1; i<=n; ++i) ++c[x[i]];
                for (int i=2; i<=m; ++i) c[i]+=c[i-1];
                for (int i=n; i>=1; --i) sa[c[x[y[i]]]--]=y[i],y[i]=0;
                swap(x,y);
                x[sa[1]]=1;
                num=1;
                for (int i=2; i<=n; ++i)
                    if((y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]))x[sa[i]]=num;
                    else x[sa[i]]=++num;
                if (num==n) break;
                m=num;
            }
            int k=0;
            for (int i=1; i<=n; ++i) rk[sa[i]]=i;
            for (int i=1; i<=n; ++i) {
                if (rk[i]==1) continue;
                if (k) --k;
                int j=sa[rk[i]-1];
                while (j+k<=n && i+k<=n && d[i+k]==d[j+k]) ++k;
                height[rk[i]]=k;
            }
        }
    
    }A;
    bool check(int len){
    //    cout<<len<<endl;
        for(register int i=1;i<=A.n;i++){
            if(A.height[i]<len)continue;
            for(register int i=0;i<=n;i++)f[i]=0;
            if(++f[loc[A.sa[i-1]]]==1)f[0]++;
    //        cout<<A.sa[i-1]<<"*"<<endl;
    //        cout<<n<<"xx"<<endl;
            while(i<=A.n&&A.height[i]>=len){
    //            cout<<"yes"<<endl;
                if(++f[loc[A.sa[i]]]==1)f[0]++;
    //            cout<<A.sa[i]<<"*"<<endl;
                i++;
                if(f[0]==n)return 1;
            }
    //        cout<<f[0]<<"&&"<<len<<endl;
        }
    //    cout<<endl;
        return 0;
    }
    int main(){
        scanf("%d",&n);
        a[0][0]=0x3f3f3f3f;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i][0]);
            for(int j=1;j<=a[i][0];j++){
                scanf("%d",&a[i][j]);
                A.d[++cnt]=a[i][j];
                loc[cnt]=i;
            }
            A.d[++cnt]=10000;
            loc[cnt]=i;
            if(a[0][0]>a[i][0])a[0][0]=a[i][0];
        }
        A.d[0]=10000;
    //    for(int i=1;i<=cnt;i++)cout<<A.d[i]<<" ";cout<<endl;
        A.n=cnt;
        for(int i=cnt;i;i--)A.d[i]-=A.d[i-1],b[i]=A.d[i];
    
        sort(b+1,b+cnt+1);
        b[0]=1;
        for(int i=2;i<=cnt;i++)if(b[i]!=b[i-1])b[++b[0]]=b[i];
        for(int i=1;i<=cnt;i++)A.d[i]=lower_bound(b+1,b+b[0]+1,A.d[i])-b;
        A.m=b[0];
    
    //    for(int i=1;i<=cnt;i++)cout<<A.d[i]<<" ";cout<<endl;
    
        A.getsa();
    //    for(int i=1;i<=cnt;i++)cout<<A.rk[i]<<" "<<A.sa[i]<<" "<<A.height[A.rk[i]]<<endl;
        int l=1,res=0,r=a[0][0],mid;
    
        while(l<=r){
            mid=(l+r)>>1;
    //        cout<<mid<<"^^^"<<endl;
            if(check(mid))res=mid,l=mid+1;
            else r=mid-1;
        }
        res++;
        cout<<res<<endl;
        return 0;
    }