[HEOI2016/TJOI2016]字符串

· · 题解

不知道更好还是更差的阅读体验

题目描述

给定长度为 n 的由小写字母组成的字符串 s，有 m 个询问，每次询问给定 a,b,c,d，求 s[a\ldots b] 的所有子串与 s[c\ldots d] 的最长公共前缀。

数据范围：1\le n,m\le10^5，1\le a<b\le n，1\le c<d\le n。

时间限制：2000\operatorname{ms}。

Solution

对于每个子串求 LCP 最大值比较复杂，时间复杂度为 \Theta(n^2\log n)，难以接受。

有一个很显然的性质：若 k 为可行答案，则任何比 k 小的值都为可行答案。

因此考虑二分。二分答案的最大值，假设当前答案为 len，会有如下的性质：

  1. 我们可以找到一个子串 ans 完全位于 [a,b] 之间，则 ans 的开头应该位于 [a,b-len+1] 之间。

由 height 数组的性质，我们可以发现，满足第二个性质的 ans 开头一定是一段包含 c 的连续区间。

我们可以二分出这个区间，然后检验第一个性质是否成立，这步可以通过主席树来实现。主席树存储可能存在答案的区间内是否有 i 使 sa[i]\in[a,b-len+1]。

时间复杂度为 \Theta(n\log^2n)，期望得分 100\operatorname{pts}。

Code（实现极丑）

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=100010;
char s[maxn];
int sa[maxn],c[maxn],x[maxn],y[maxn],n,m;
int rk[maxn],height[maxn];
int q,tot,st[maxn][18],lg2[maxn],root[maxn];
template<class T>inline T Min(const T &a,const T &b){return a<b?a:b;}
inline void GetSA(){
    for(int i=1;i<=n;++i)++c[x[i]=s[i]];
    for(int i=2;i<=m;++i)c[i]+=c[i-1];
    for(int i=n;i;--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;--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)
            x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
        if(num==m)break;
        m=num;
    }
}
inline void GetHeight(){
    for(int i=1;i<=n;++i)rk[sa[i]]=i;
    for(int i=1,k=0;i<=n;++i){
        if(rk[i]==1)continue;
        if(k)--k;
        int 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{
    int lc,rc,v;
}tr[maxn*20];
inline void pushup(int u){
    tr[u].v=tr[tr[u].lc].v+tr[tr[u].rc].v;
}
inline int Insert(int p,int l,int r,int x){
    int u=++tot;
    if(l==r){tr[u].v=tr[p].v+1;return u;}
    int mid=(l+r)>>1;
    if(x<=mid){
        tr[u].rc=tr[p].rc;
        tr[u].lc=Insert(tr[p].lc,l,mid,x);
    }
    else{
        tr[u].lc=tr[p].lc;
        tr[u].rc=Insert(tr[p].rc,mid+1,r,x);
    }
    pushup(u);
    return u;
}
inline int query(int p,int q,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr)return tr[q].v-tr[p].v;
    int mid=(l+r)>>1,ans=0;
    if(ql<=mid)ans=query(tr[p].lc,tr[q].lc,l,mid,ql,qr);
    if(mid<qr)ans+=query(tr[p].rc,tr[q].rc,mid+1,r,ql,qr);
    return ans;
}
inline void InitST(){
    for(int i=1;i<=n;++i)st[i][0]=height[i],lg2[i]=log2(i);
    for(int i=1;i<18;++i)
        for(int j=1;j+(1<<i)-1<=n;++j)
            st[j][i]=Min(st[j][i-1],st[j+(1<<(i-1))][i-1]);
}
inline int queryST(int l,int r){
    if(l>r)swap(l,r);
    if(l==r)return n-l+1;
    ++l;
    int t=lg2[r-l+1];
    return Min(st[l][t],st[r-(1<<t)+1][t]);
}
inline bool check(int len,int a,int b,int c,int d){
    int l=1,r=rk[c],ql,qr;
    while(l<r){
        int mid=(l+r)>>1;
        if(queryST(mid,rk[c])<len)l=mid+1;
        else r=mid;
    }
    ql=r;
    l=rk[c],r=n;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(queryST(rk[c],mid)<len)r=mid-1;
        else l=mid;
    }
    qr=l;
    if(query(root[ql-1],root[qr],1,n,a,b-len+1)>0)return true;
    else return false;
}
inline int solve(int a,int b,int c,int d){
    int l=0,r=Min(b-a+1,d-c+1);
    while(l<r){
        int mid=(l+r+1)>>1;
        if(check(mid,a,b,c,d))l=mid;
        else r=mid-1;
    }
    return l;
}
int main(){
    scanf("%d%d",&n,&q);
    scanf("%s",s+1);m='z';
    GetSA();GetHeight();
    for(int i=1;i<=n;++i)
        root[i]=Insert(root[i-1],1,n,sa[i]);
    InitST();
    while(q--){
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        printf("%d\n",solve(a,b,c,d));
    }
    return 0;
}