zcmimi's blog
查看原题

点击跳转

连接所有字符串(cnt个),中间用特殊字符隔开

给每个位置标记所属字符串

然后求出sa,rnk,height数组

我们要找出cnt个所属字符串不同的后缀,让他们\operatorname{LCP}最长

可以用双指针+单调队列的方式实现

单调队列记录当前区间最小的height,单调递增,双指针移动右指针的同时维护单调队列,移动右指针后判断是否可以移动左指针,并重复到无法移动,同时对应弹出单调队列的队头

#include<bits/stdc++.h>
const int N=10111;
int cnt,n,m,sa[N],rnk[N],height[N],tax[N],tp[N];
char s[N];
void qsort(){
    for(int i=0;i<=m;++i)tax[i]=0;
    for(int i=1;i<=n;++i)++tax[rnk[i]];
    for(int i=1;i<=m;++i)tax[i]+=tax[i-1];
    for(int i=n;i;--i)
        sa[tax[rnk[tp[i]]]--]=tp[i];
}
void suffix(){
    m=100;
    for(int i=1;i<=n;++i)tp[i]=i,rnk[i]=s[i]-'a'+1;
    qsort();
    for(int w=1,p=0;p<n;m=p,w<<=1){
        p=0;
        for(int i=1;i<=w;++i)tp[++p]=n-w+i;
        for(int i=1;i<=n;++i)if(sa[i]>w)
            tp[++p]=sa[i]-w;
        qsort();
        std::swap(tp,rnk);
        rnk[sa[1]]=p=1;
        for(int i=2;i<=n;++i)
            rnk[sa[i]]=p+=tp[sa[i]]^tp[sa[i-1]]||tp[sa[i]+w]^tp[sa[i-1]+w];
    }
}
void get_height(){
    for(int i=1,k=0;i<=n;++i){
        if(k)--k;
        int j=sa[rnk[i]-1];
        while(s[i+k]==s[j+k]&&i+k<=n&&j+k<=n)++k;
        height[rnk[i]]=k;
    }
}
int col[N],L[N],R[N],v[N],tot,q[N],h=1,t;
void add(int x){if(col[x])if(++v[col[x]]==1)++tot;}
void del(int x){if(col[x])if(!--v[col[x]])--tot;}
void cmax(int &x,int y){if(x<y)x=y;}
int main(){
    scanf("%d",&cnt);
    for(int i=1;i<=cnt;++i)
        L[i]=n+1,
        scanf("%s",s+n+1),
        s[n=strlen(s+1)+1]=i+'a'-1,
        R[i]=n-1;
    suffix();
    get_height();
    for(int i=1;i<=cnt;++i)
        for(int j=L[i];j<=R[i];++j)
            col[rnk[j]]=i;
    int l=1,ans=0;
    add(1);
    for(int r=2;r<=n;++r){
        while(h<=t&&height[q[t]]>=height[r])--t;
        q[++t]=r;
        add(r);
        if(tot==cnt){
            while(tot==cnt&&l<r)del(l++);
            add(--l);
        }
        while(h<=t&&q[h]<=l)++h;
        if(tot==cnt)cmax(ans,height[q[h]]);
    }
    printf("%d\n",ans);
}
LG 5546 [POI2000]公共串
comment评论
Search
search