【BZOJ-4556】字符串后缀数组+二分+主席树 / 后缀自动机+线段树合并+二分

2022-12-18 18:50:09

4556: [Tjoi2016&Heoi2016]字符串

Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 657 Solved: 274
[Submit][Status][Discuss]

Description

佳媛姐姐过生日的时候，她的小伙伴从某东上买了一个生日礼物。生日礼物放在一个神奇的箱子中。箱子外边写了一个长为n的字符串s，和m个问题。佳媛姐姐必须正确回答这m个问题，才能打开箱子拿到礼物，升职加薪，出任CEO，嫁给高富帅，走上人生巅峰。每个问题均有a,b,c,d四个参数，问你子串s[a..b]的所有子串和s[c..d]的最长公共前缀的长度的最大值是多少？佳媛姐姐并不擅长做这样的问题，所以她向你求助，你该如何帮助她呢？

Input

输入的第一行有两个正整数n,m，分别表示字符串的长度和询问的个数。接下来一行是一个长为n的字符串。接下来m行，每行有4个数a,b,c,d，表示询问s[a..b]的所有子串和s[c..d]的最长公共前缀的最大值。1<=n,m<=100,000,字符串中仅有小写英文字母，a<=b,c<=d,1<=a,b,c,d<=n

Output

对于每一次询问，输出答案。

Sample Input

5 5
aaaaa
1 1 1 5
1 5 1 1
2 3 2 3
2 4 2 3
2 3 2 4

Sample Output

1
1
2
2
2

HINT

Source

Solution

做过类似的题就会很好做了。

考虑后缀数组的做法，就是二分一个答案mid，那么在[a,b]中答案子串的起点一定只能出现在[a,b-mid+1]，那么只需要判定和Suffix(c)的LCP>=mid的子串是否有[a,b-mid+1]中的即可。

然后考虑LCP在Height数组上从Suffix(c)向左右单调不增的，所以可以二分出满足与Suffix(c)的LCP>=mid的区间[L,R]，然后利用主席树去查是否有[a,b-mid+1]中的。

同样可以利用后缀自动机做，因为是公共前缀，所以可以考虑把串翻转转化成后缀，利用线段树合并预处理出每个节点的状态，同理二分答案，利用预处理的查询即可。

后缀自动机的做法常数较小，实际跑起来效果明显优于后缀数组做法。

Code

后缀数组

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

inline int read()

{

    int x=0,f=1; char ch=getchar();

    while (ch<'0' || ch>'9') {if (ch=='-')  f=-1; ch=getchar();}

    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}

    return x*f;

}

#define MAXN 100010

int N,M;

char S[MAXN];

int R[MAXN],SA[MAXN],height[MAXN],rank[MAXN],t1[MAXN],t2[MAXN],st[MAXN];

inline void Sort(int *x,int *y,int *sa,int L,int M)

{

    for (int i=0; i<=M; i++) st[i]=0;

    for (int i=0; i<L; i++) st[x[y[i]]]++;

    for (int i=1; i<=M; i++) st[i]+=st[i-1];

    for (int i=L-1; i>=0; i--) sa[--st[x[y[i]]]]=y[i];

}

inline void DA(int *r,int *sa,int L,int M)

{

    int *x=t1,*y=t2,*t,i,j,p;

    for (int i=0; i<L; i++) x[i]=r[i],y[i]=i;

    Sort(x,y,sa,L,M);

    for (j=1,p=1; j<L && p<L; j<<=1,M=p-1)

        {

            for (p=0,i=L-j; i<L; i++) y[p++]=i;

            for (i=0; i<L; i++) if (sa[i]>=j) y[p++]=SA[i]-j;

            Sort(x,y,sa,L,M);

            for (t=x,x=y,y=t,i=1,x[sa[0]]=0,p=1; i<L; i++)

                x[sa[i]]=y[sa[i-1]]==y[sa[i]] && y[sa[i-1]+j]==y[sa[i]+j]? p-1:p++;

        }

}

inline void Height(int *r,int *sa,int *rank,int *h,int L)

{

    h[1]=0;

    for (int i=1; i<=L; i++) rank[sa[i]]=i;

    for (int i=1,k=0,j; i<=L; h[rank[i++]]=k)

        for (k? --k:k=0,j=sa[rank[i]-1]; r[j+k]==r[i+k]; k++);

}

int log_2[MAXN],dp[MAXN][21];

inline void St(int L)

{

    log_2[0]=-1;

    for (int i=1; i<=L; i++)

        if (i&(i-1))

            log_2[i]=log_2[i-1];

        else

            log_2[i]=log_2[i-1]+1;

    for (int i=0; i<=L; i++) dp[i][0]=height[i+1];

    for (int j=1; (1<<j)<=L; j++)

        for (int i=0; i+(1<<j)-1<=L; i++)

            dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);

}

inline int RMQ(int l,int r) {if (l==r) return N-SA[l]; int k=log_2[r-l]; return min(dp[l][k],dp[r-(1<<k)][k]);}

inline int LCP(int l,int r) {if (l>r) swap(l,r); return RMQ(l,r);}

int sz,sum[MAXN*20],lson[MAXN*20],rson[MAXN*20],root[MAXN];

inline void Insert(int &x,int y,int l,int r,int pos)

{

    x=++sz; sum[x]=sum[y]+1;

    if (l==r) return;

    lson[x]=lson[y]; rson[x]=rson[y];

    int mid=(l+r)>>1;

    if (pos<=mid) Insert(lson[x],lson[y],l,mid,pos);

        else Insert(rson[x],rson[y],mid+1,r,pos);

}

inline int Query(int x,int y,int l,int r,int L,int R)

{

    if (L<=l && R>=r) return sum[y]-sum[x];

    int mid=(l+r)>>1,re=0;

    if (L<=mid) re+=Query(lson[x],lson[y],l,mid,L,R);

    if (R>mid) re+=Query(rson[x],rson[y],mid+1,r,L,R);

    return re;

}

inline int GetL(int x,int y)

{

    int l=1,r=rank[x],re=-1;

    while (l<=r) {

        int mid=(l+r)>>1;

        if (RMQ(mid,rank[x])>=y) r=mid-1,re=mid;

            else l=mid+1;

    }

    return re;

}

inline int GetR(int x,int y)

{

    int l=rank[x],r=N,re=-1;

    while (l<=r) {

        int mid=(l+r)>>1;

        if (RMQ(rank[x],mid)>=y) l=mid+1,re=mid;

            else r=mid-1;

    }

    return re;

}

int main()

{

    N=read(),M=read();

    scanf("%s",S+1);

    for (int i=1; i<=N; i++) R[i]=S[i]-'a'+1;

    DA(R,SA,N+1,28); Height(R,SA,rank,height,N); St(N);

//  for (int i=1; i<=N; i++) printf("%d ",SA[i]); puts("");

//  for (int i=1; i<=N; i++) printf("%d ",rank[i]); puts("");

    for (int i=1; i<=N; i++) Insert(root[i],root[i-1],1,N,SA[i]);

    while (M--) {

        int a=read(),b=read(),c=read(),d=read();

        int l=1,r=min(b-a+1,d-c+1),ans=0,L,R;

        while (l<=r) {

            int mid=(l+r)>>1;

            L=GetL(c,mid); R=GetR(c,mid);

            if (L==-1) L=rank[c];

            if (R==-1) R=rank[c];

            if (Query(root[L-1],root[R],1,N,a,b-mid+1)) l=mid+1,ans=mid;

            else r=mid-1;

        }

        printf("%d\n",ans);

    }

    return 0;

}

后缀自动机

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

inline int read()

{

    int x=0,f=1; char ch=getchar();

    while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}

    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}

    return x*f;

}

#define MAXN 100010 

int N,M;

char S[MAXN];

struct SgtNode{

    int lson,rson;

}tree[MAXN*40];

int cnt,root[MAXN<<1];

inline void Insert(int &x,int l,int r,int pos)

{

    x=++cnt;

    if (l==r) return;

    int mid=(l+r)>>1;

    if (pos<=mid) Insert(tree[x].lson,l,mid,pos);

        else Insert(tree[x].rson,mid+1,r,pos);

}

inline int Merge(int x,int y)

{

    if (!x || !y) return x|y;

    int z=++cnt;

    if (x==y) return x;

    tree[z].lson=Merge(tree[x].lson,tree[y].lson);

    tree[z].rson=Merge(tree[x].rson,tree[y].rson);

    return z;

}

inline int Query(int x,int l,int r,int L,int R)

{

    if (!x) return 0;

    if (L<=l && R>=r) return 1;

    int mid=(l+r)>>1,re=0;

    if (L<=mid) re|=Query(tree[x].lson,l,mid,L,R);

    if (R>mid) re|=Query(tree[x].rson,mid+1,r,L,R);

    return re;

}

int len[MAXN<<1],son[MAXN<<1][26],par[MAXN<<1],st[MAXN],id[MAXN<<1],sz=1,rt=1,last=1,father[21][MAXN<<1];

inline void Extend(int c)

{

    int cur=++sz,p=last;

    len[cur]=len[p]+1;

    while (p && !son[p][c]) son[p][c]=cur,p=par[p];

    if (!p) par[cur]=rt;

    else {

        int q=son[p][c];

        if (len[p]+1==len[q]) par[cur]=q;

        else {

            int nq=++sz;

            memcpy(son[nq],son[q],sizeof(son[nq]));

            len[nq]=len[p]+1; par[nq]=par[q];

            while (p && son[p][c]==q) son[p][c]=nq,p=par[p];

            par[q]=par[cur]=nq;

        }

    }

    last=cur;

}

inline void Sort()

{

    for (int i=0; i<=N; i++) st[i]=0;

    for (int i=1; i<=sz; i++) st[len[i]]++;

    for (int i=1; i<=N; i++) st[i]+=st[i-1];

    for (int i=1; i<=sz; i++) id[st[len[i]]--]=i;

    for (int i=sz; i>=1; i--) {

        int x=id[i];

        root[par[x]]=Merge(root[par[x]],root[x]);

    }

    for (int i=1; i<=sz; i++) {

        int x=id[i];

        father[0][x]=par[x];

        for (int j=1; j<=20; j++)

            father[j][x]=father[j-1][father[j-1][x]];

    }

}

inline bool Check(int x,int mid,int a,int b)

{

    for (int i=20; i>=0; i--)

        if (len[father[i][x]]>=mid) x=father[i][x];

    return Query(root[x],1,N,a,b);

}

int pos[MAXN];

int main()

{

    N=read(),M=read();

    scanf("%s",S+1); reverse(S+1,S+N+1);

    for (int i=1; i<=N; i++) Extend(S[i]-'a'),pos[i]=last,Insert(root[last],1,N,i);

    Sort();

    while (M--) {

        int a=read(),b=read(),c=read(),d=read();

        a=N-a+1,b=N-b+1,c=N-c+1,d=N-d+1; swap(a,b); swap(c,d);

        int l=1,r=min(d-c+1,b-a+1),ans=0;

        while (l<=r) {

            int mid=(l+r)>>1;

            if (Check(pos[d],mid,a+mid-1,b)) l=mid+1,ans=mid;

                else r=mid-1;

        }

        printf("%d\n",ans);

    }

    return 0;

}

码农公寓