Substring 题解

· · 题解

\color{purple}\mathrm{Substring} 题解

subtask 1：

当 T 中所有字母相同时。设 x 为 T 中的字母，k 为 S 中 x 最多连续出现的次数。则每次询问的答案为 \min(r-l+1,k)。

subtask 2：

直接暴力枚举即可。

subtask 3：

对于每个询问，我们将 S 串和 T 串询问的子串拼起来，中间用另一种符号隔开，然后跑一遍 SA，求出 height 数组，及 h_i 表示后缀排序中第 i 和第 i-1 个的最长公共前缀，答案为 \max\{h_i\}。时间复杂度 \mathcal{O}(Qn\log n)（倍增做法）。

subtask 4：

当 S 中所有字母相同时。设 x 为 S 中的字母，每次询问即是求出 T 的一个子串中 x 最多连续出现的次数。

定义 k_i 为以 T_i 为开头，x 最多连续出现的次数。每次询问即是求出 \max\limits_{i=l}^r\{k_i\}。但这可能出现越界情况，即 i+k_i-1>r。为了避免越界，可采取二分答案，用 rmq 询问 \max\limits_{i=l}^{r-mid+1}\{k_i\} ，如果结果大于等于 mid，令 ans=mid,l=mid+1；否则令 r=mid-1 。这样就能保证不出现越界。时间复杂度 \mathcal{O}(Q\log n)。

subtask 5：

subtask 4 已经很接近正解了，只需将 S,T 用分隔符隔开拼接起来，跑一遍 SA。定义 k_i 为以 T_i 为开头，与 S 串最长公共前缀的长度。我们在后缀排序中，对于每个 T 串中的字母，找出他前面与后面第一个 S 串中的字母，分别记为 p,q。 k_i 即为 \max(lcp(i,p),lcp(i,q)) ( lcp(i,j) 表示以 T_i 和 S_j 为后缀最长公共前缀的长度)。然后我们用 subtask 4 的方法二分答案即可求解。时间复杂度 \mathcal{O}(Q\log n)。

AC Code

#include<iostream>
#include<cstdio>
using namespace std;
int p=1,Q,n,len,ans,bl[1000005],sa[2][1000005],rk[2][1000005],v[1000005],f[1000005],g[20][1000005],logg[1000005];
string s,t,a;
inline void read(int &x) {
    x=0;int f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    x*=f;
}
inline void mul(int *sa,int *rk,int *SA,int *RK,int n,int k) {
    for(int i=1;i<=n;i++)v[rk[sa[i]]]=i;
    for(int i=n;i>=1;i--)if(sa[i]>k)SA[v[rk[sa[i]-k]]--]=sa[i]-k;
    for(int i=n-k+1;i<=n;i++)SA[v[rk[i]]--]=i;
    for(int i=1;i<=n;i++)RK[SA[i]]=RK[SA[i-1]]+(rk[SA[i]]!=rk[SA[i-1]]||rk[SA[i]+k]!=rk[SA[i-1]+k]);
}
inline void pre() {
    for(int i=1;i<=n;i++)v[a[i]]++;
    for(int i=1;i<=130;i++)v[i]+=v[i-1];
    for(int i=1;i<=n;i++)sa[p][v[a[i]]--]=i;
    for(int i=1;i<=n;i++)rk[p][sa[p][i]]=rk[p][sa[p][i-1]]+(a[sa[p][i]]!=a[sa[p][i-1]]);
    for(int i=1;i<n;i<<=1,p^=1)mul(sa[p],rk[p],sa[p^1],rk[p^1],n,i);
    for(int i=1,k=0;i<=n;i++) {
        int j=sa[p][rk[p][i]-1];
        while(a[i+k]==a[j+k])k++;
        f[rk[p][i]]=k;
        if(k)k--;
    }
}
inline void st() {
    for(int i=1;1<<i<=n;i++)
        for(int j=1;j<=n-(1<<i)+1;j++)
            g[i][j]=max(g[i-1][j],g[i-1][j+(1<<i-1)]);
}
inline int ask(int l,int r) {
    if(l>r)swap(l,r);
    int k=logg[r-l+1];
    return max(g[k][l],g[k][r-(1<<k)+1]);
}
inline int solve(int ql,int qr) {
    ql+=len+1,qr+=len+1; 
    int l=0,r=qr-ql+1,ans=0,mid;
    while(l<=r) {
        mid=l+r>>1;
        if(ask(ql,qr-mid+1)>=mid)l=mid+1,ans=mid;
        else r=mid-1;
    }
    return ans;
}
signed main() {
    cin>>s>>t;
    read(Q);
    len=s.size();
    a=' '+s+'#'+t,n=a.size()-1;
    for(int i=2;i<=n;i++) {
        logg[i]=logg[i-1];
        if((1<<logg[i]+1)<=i)logg[i]++;
    }
    for(int i=1;i<=len;i++)bl[i]=1;
    for(int i=len+2;i<=n;i++)bl[i]=2;
    pre();
    int minn=0x7fffffff;
    for(int i=1;i<=n;i++) {
        if(!bl[sa[p][i]])continue;
        if(bl[sa[p][i]]==2) {
            minn=min(minn,f[i]);
            g[0][sa[p][i]]=minn;
        }else minn=0x7fffffff;
    }
    minn=0;
    for(int i=n;i>=1;i--) {
        if(!bl[sa[p][i]])continue;
        if(bl[sa[p][i]]==2)g[0][sa[p][i]]=max(g[0][sa[p][i]],minn); 
        else minn=0x7fffffff;
        minn=min(minn,f[i]);
    }
    st();
    while(Q--) {
        int l,r;
        read(l),read(r);
        printf("%d\n",solve(l,r));
    }
    return 0;
}

验题大佬 leihonglongyin 似乎有 \mathcal{O}(1) 查询的解法%%%。