Luogu

LOJ

分析

考虑二分答案 $mid$，则我们需要判定是否存在一个 $p\in[a,b-mid+1]$，满足 $\operatorname{lcp}(suf(p),suf(c))\geq mid$。

既然有 LCP，可以考虑后缀数组，则 $\operatorname{lcp}(suf(p),suf(c))\geq mid$ 相当于 $\min_{i=rk_p+1}^{rk_c}height_i$（或者 $\min_{i=rk_c+1}^{rk_p}height_i$，取决于 $rk_c$ 和 $rk_p$ 的大小关系）$\geq mid$。

而 $rk_c$ 是确定的，不难发现满足条件的 $rk_p$ 是一段区间，可以通过二分求出。假设这个范围是 $[x,y]$。

现在的问题变为判断是否存在一个 $p\in [a,b-mid+1]$ 满足 $rk_p\in[x,y]$。可以以 $rk_i$ 为下标建一棵主席树，则我们只需要询问 $[a,b-mid+1]$ 版本中 $[x,y]$ 的和并判断是否为 $0$ 即可。

然而二分+主席树并没有直接暴力找满足条件的区间跑得快

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,Q; char s[N];

namespace SA {
    int sa[N],rk[N],height[N];
    int x[N],y[N],z[N];
    int lg[N],f[17][N];
    void SuffixSort() {
        int m=122;
        for (int i=1;i<=n;++i) ++z[x[i]=s[i]];
        for (int i=2;i<=m;++i) z[i]+=z[i-1];
        for (int i=n;i;--i) sa[z[x[i]]--]=i;
        for (int k=1;k<=n;k<<=1) {
            int p=0;
            for (int i=n-k+1;i<=n;++i) y[++p]=i;
            for (int i=1;i<=n;++i) if (sa[i]>k) y[++p]=sa[i]-k;
            for (int i=1;i<=m;++i) z[i]=0;
            for (int i=1;i<=n;++i) ++z[x[i]];
            for (int i=2;i<=m;++i) z[i]+=z[i-1];
            for (int i=n;i;--i) sa[z[x[y[i]]]--]=y[i],y[i]=0;
            swap(x,y),x[sa[1]]=p=1;
            for (int i=2;i<=n;++i)
                x[sa[i]]=(y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k])?p:++p;
            if (p==n) break; m=p;
        }
    }
    void GetHeight() {
        for (int i=1;i<=n;++i) rk[sa[i]]=i;
        for (int i=1,j=0;i<=n;++i) {
            if (j) --j; int p=sa[rk[i]-1];
            for (;s[i+j]==s[p+j];++j);
            height[rk[i]]=j;
        }
    }
    void buildST() {
        for (int i=2;i<=n;++i) lg[i]=lg[i>>1]+1;
        for (int i=1;i<=n;++i) f[0][i]=height[i];
        for (int i=1;i<17;++i)
            for (int j=1;j<=n;++j)
                f[i][j]=min(f[i-1][j],f[i-1][j+(1<<(i-1))]);
    }
    int LCP_(int l,int r) {
        int t=lg[r-l+1];
        return min(f[t][l],f[t][r-(1<<t)+1]);
    }
    int LCP(int x,int y) {
        if (rk[x]>rk[y]) swap(x,y);
        return LCP_(rk[x]+1,rk[y]);
    }
    void build() { SuffixSort(); GetHeight(); buildST(); }
}

#define ls(o) ch[o][0]
#define rs(o) ch[o][1]
int rt[N],tot=0;
int ch[N*30][2],sz[N*30];
void modify(int& o,int f,int l,int r,int p) {
    o=++tot,ls(o)=ls(f),rs(o)=rs(f),sz[o]=sz[f]+1;
    if (l==r) return;
    int mid=(l+r)>>1;
    if (p<=mid) modify(ls(o),ls(f),l,mid,p);
    else modify(rs(o),rs(f),mid+1,r,p);
}
int query(int o,int l,int r,int ql,int qr) {
    if (!o) return 0;
    if (ql<=l&&r<=qr) return sz[o];
    int mid=(l+r)>>1,res=0;
    if (ql<=mid) res+=query(ls(o),l,mid,ql,qr);
    if (qr>mid) res+=query(rs(o),mid+1,r,ql,qr);
    return res;
}
#undef ls
#undef rs

int findL(int p,int l) {
    int L=1,R=p;
    while (L<R) {
        int mid=(L+R)>>1;
        if (SA::LCP_(mid+1,p)>=l) R=mid;
        else L=mid+1;
    }
    return L;
}
int findR(int p,int l) {
    int L=p,R=n;
    while (L<R) {
        int mid=(L+R+1)>>1;
        if (SA::LCP_(p+1,mid)>=l) L=mid;
        else R=mid-1;
    }
    return L;
}

int main() {
    n=read(),Q=read(); scanf("%s",s+1);
    SA::build();
    for (int i=1;i<=n;++i)
        modify(rt[i],rt[i-1],1,n,SA::rk[i]);
    while (Q--) {
        int a=read(),b=read(),c=read(),d=read();
        int L=0,R=min(b-a+1,d-c+1);
        while (L<R) {
            int mid=(L+R+1)>>1;
            int x=findL(SA::rk[c],mid),y=findR(SA::rk[c],mid);
            if (query(rt[b-mid+1],1,n,x,y)-query(rt[a-1],1,n,x,y)) L=mid;
            else R=mid-1;
        }
        printf("%d\n",L);
    }
    return 0;
}