题解 P5341 【[TJOI2019]甲苯先生和大中锋的字符串】

· · 题解

Update1:修了一点小锅

[TJOI2019]甲苯先生和大中锋的字符串

提供一个 \mathcal{SA} 的做法。

题面有点绕，大意是找出仅出现 k 次的子串集合，然后统计出现最多的子串长度。

考虑如何求出子串集合，先建好 height 数组，问题可以转化为在 height 数组上找一个长度为 k 的连续区间，求在排序后的后缀中仅能出现在这段区间内的“公共前缀”有那些。

设区间 [i,i+k-1] 的“公共前缀”长为 l ，考虑 l 的范围，显然 l 最大只能是 \text{lcp}_{i}^{i+k-1} , 也就是经过排序的后缀在这段区间的最长公共前缀。

根据 height 数组的定义，有 \text{lcp}_{i}^{i+k-1}=\min_{j=i+1}^{i+k-1}\{h_{j}\} ，h 表示 height 数组，对于前面这个式子可以用一个能维护 RMQ 问题的数据结构就行。

接下来考虑 l 的下界，先给出结论，若要满足这段“公共前缀”不能在区间 [i,i+k-1] 出现过，则 l > \max(h_i,h_{i+k}) 。

感性证明一下，若 l \leq h_i,h_{i+k} ，则说明长度为 l 的“公共前缀”已经超过了 k 个，是与“仅出现 k 次”矛盾的。

于是我们可以对 height 数组做一个类似于滑动窗口的东西，用差分数组维护每个区间对应的 l 的值域，跑完之后求那个长度出现最多即可。

既然你能找到这题，我相信你能瞬间做出来的。

Code: 
#include<bits/stdc++.h>
typedef long long LL;
typedef long double LD;
using namespace std;
const LL N=100010,INF=0x3f3f3f3f;
inline LL Max(LL x,LL y){return x>y?x:y;}
inline LL Min(LL x,LL y){return x<y?x:y;}
inline void Swap(LL &x,LL &y){x^=y^=x^=y;}
LL T,n,m,k,cf[N];
char s[N];
namespace SA{
LL sa[N],height[N],c[N],x[N],y[N],rk[N];
void get_sa(){
    for(LL i=1;i<=m;i++)c[i]=0;
    for(LL i=1;i<=n;i++)c[x[i]=s[i]]++;
    for(LL i=2;i<=m;i++)c[i]+=c[i-1];
    for(LL i=n;i>=1;i--)sa[c[x[i]]--]=i;
    for(LL w=1;w<=n;w<<=1){
        LL num=0;
        for(LL i=n-w+1;i<=n;i++)y[++num]=i;
        for(LL i=1;i<=n;i++)
            if(sa[i]>w)y[++num]=sa[i]-w;
        for(LL i=1;i<=m;i++)c[i]=0;
        for(LL i=1;i<=n;i++)c[x[i]]++;
        for(LL i=2;i<=m;i++)c[i]+=c[i-1];
        for(LL i=n;i>=1;i--)sa[c[x[y[i]]]--]=y[i],y[i]=0;
        std::swap(x,y);
        x[sa[1]]=num=1;
        for(LL i=2;i<=n;i++)
            x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+w]==y[sa[i-1]+w])?num:++num;
        if(num==n)break;
        m=num;
    }
}
void get_height(){
    for(LL i=1;i<=n;i++)rk[sa[i]]=i;
    for(LL i=1,k=0;i<=n;i++){
        if(rk[i]==1)continue;
        if(k)k--;
        LL j=sa[rk[i]-1];
        while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])k++;
        height[rk[i]]=k;
    }
}
}
struct SegmentTree{
    LL l,r;
    LL mn;
    #define l(x) tree[x].l
    #define r(x) tree[x].r
    #define mn(x) tree[x].mn
}tree[N<<2];
void Pushup(LL x){
    mn(x)=Min(mn(x<<1),mn(x<<1|1));
}
void Build(LL x,LL l,LL r){
    l(x)=l,r(x)=r;mn(x)=0;
    if(l==r){mn(x)=SA::height[l];return;}
    LL mid=(l+r)>>1;
    Build(x<<1,l,mid);
    Build(x<<1|1,mid+1,r);
    Pushup(x);
}
LL Query(LL x,LL L,LL R){
    LL l=l(x),r=r(x);
    if(L<=l&&r<=R)return mn(x);
    LL mid=(l+r)>>1;
    LL val=INF;
    if(L<=mid)val=Min(val,Query(x<<1,L,R));
    if(R>mid)val=Min(val,Query(x<<1|1,L,R));
    return val;
}
int main(){
    scanf("%lld",&T);
    while(T--){
        scanf("%s%lld",s+1,&k); 
        n=strlen(s+1);m=122;
        memset(cf,0,sizeof(cf));
        SA::height[n+1]=0;
        SA::get_sa();
        SA::get_height();
        Build(1,1,n);
        for(LL i=1;i+k-1<=n;i++){
            LL l=i,r=i+k-1,L,R;
            if(l+1>r)R=n-SA::sa[r]+1;
            else R=Query(1,l+1,r);
            L=Max(SA::height[l],SA::height[r+1])+1;
            if(L<=R)++cf[L],--cf[R+1];
        }
        LL ans=-1,maxv=1;
        for(LL i=1;i<=n;i++){
            cf[i]+=cf[i-1];
            if(cf[i]>=maxv)ans=i,maxv=cf[i];
        }
        printf("%lld\n",ans);
    }
    return 0;
}