[HEOI2016/TJOI2016]字符串 题解

SA+二分+主席树

Statement

\(q\) 次询问 \(s[a\dots b]\) 的所有子串和 \(s[c\dots d]\) 的最长公共前缀最大值

\(n,q\le 10^5\)

Solution

其实感觉算不上黑题

看到 LCP，容易想到 SA，管都不管，先套一个 SA

SA 套路二分答案，然后把 height 数组分组

设 \(l=\min\{i|height[i]>=mid\},r=\max\{i|height[i]>mid\}\) 且 \(l,r\) 和 \(rk[c]\) 在一个组内

容易发现每次其实是在问是否 \(\exist i\in[l,r] ,sa[i]\in[a,b-mid+1]\)，这个可以用主席树

所以复杂度 \(O(n\log^2 n)\)， 有一点代码细节

Code

#include
#define ls t[rt].l
#define rs t[rt].r
#define mid ((l+r)>>1)
using namespace std;
const int N = 2e5+5;

// char buf[1<<23],*p1=buf,*p2=buf;
// #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
int read(){
    int s=0,w=1; char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
    while(isdigit(ch))s=s*10+(ch^48),ch=getchar();
    return s*w;
}

char s[N];
int rot[N];
int n,m,q;

struct SA{
    int sa[N],rk[N],tp[N],tax[N];
    int het[N],f[N][20],Log[N];
   
    void radix_sort(){
        for(int i=0;i<=m;++i)tax[i]=0;
        for(int i=1;i<=n;++i)tax[rk[i]]++;
        for(int i=1;i<=m;++i)tax[i]+=tax[i-1];
        for(int i=n;i>=1;--i)sa[tax[rk[tp[i]]]--]=tp[i];
    }
    void suffix_sort(){
        m=500;
        for(int i=1;i<=n;++i)
            rk[i]=s[i]-'a'+1,tp[i]=i;
        radix_sort();
        for(int w=1,p;p=0,ww)tp[++p]=sa[i]-w;
            radix_sort(),swap(rk,tp),rk[sa[1]]=p=1;
            for(int i=2;i<=n;++i)
                rk[sa[i]]=(tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+w]==tp[sa[i-1]+w])?p:++p;
        }
    }
    void get_height(){
        int k=0;
        for(int i=1;i<=n;++i){
            if(k)--k;
            int j=sa[rk[i]-1];
            while(s[i+k]==s[j+k])++k;
            het[rk[i]]=k;
        }
    }
    void ST(){
        Log[0]=-1;
        for(int i=1;i<=n;++i)
            Log[i]=Log[i>>1]+1,f[i][0]=het[i];
        for(int i=1;(1<r)return 1e9;
        int t=Log[r-l+1];
        return min(f[l][t],f[r-(1<mid)return query(mid+1,r,rs,t[p].r,L,R);
        return query(l,mid,ls,t[p].l,L,R)+query(mid+1,r,rs,t[p].r,L,R);
    }
    void build(){
        for(int i=1;i<=n;++i)
            insert(1,n,rot[i]=rot[i-1],sa.sa[i]);
    }
}seg;

signed main(){
    n=read(),q=read(),scanf("%s",s+1);
    sa.build(),seg.build();
    for(int i=1,a,b,c,d;i<=q;++i){
        a=read(),b=read(),c=read(),d=read();
        int l=0,r=min(b-a+1,d-c+1);
        while(l>1;
            bool fg=false;
            int u=sa.rk[c],up=u,down=u;
            for(int j=17,tmp;j>=0;--j){
                tmp=up-(1<0&&sa.query(tmp+1,u)>=midd)up=tmp;
                tmp=down+(1<=midd)down=tmp;
            }
            fg=seg.query(1,n,rot[down],rot[up-1],a,b-midd+1)!=0;
            if(midd==0)fg=true;
            if(fg)l=midd;
            else r=midd-1;
        }
        printf("%d\n",l);
    }
    return 0;
}