正题

题目链接:https://www.luogu.com.cn/problem/P6640

题目大意

给出两个字符串\(s,t\)。\(q\)次给出\(l,r\)询问\(s_{l\sim r}\)与\(t\)的最长公共子串。

解题思路

对于末尾的条件很好做，直接上\(SAM\)就好了，设\(f_i\)表示一个最大的数满足\(s_{i-f_i+1,i}\)是\(t\)的子串。

然后对于一个询问\(l,r\)就是相当于求\(max\{\ min\{f_{l+i-1},i\}\ \}(i\in[1,r-l+1])\)这个东西。

考虑二分一个答案\(x\)，那么在\([l,l+x-2]\)这个范围内一定不会有答案，在剩下的\([l+x-1,r]\)内取一个最大值和\(x\)做一下对比即可去掉\(min\)的条件。

用一个\(ST\)维护一下就好了，时间复杂度\(O(n+q\log n)\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=4e5+10,T=19;

int n,m,q,last,cnt,lg[N],f[N][T];

int ch[N][26],len[N],fa[N];

char s[N],t[N];

void Insert(int c){

    int p=last,np=last=++cnt;

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

    for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np;

    if(!p)fa[np]=1;

    else{

        int q=ch[p][c];

        if(len[p]+1==len[q])fa[np]=q;

        else{

            int nq=++cnt;len[nq]=len[p]+1;

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

            fa[nq]=fa[q];fa[q]=fa[np]=nq;

            for(;p&&ch[p][c]==q;p=fa[p])ch[p][c]=nq;

        }

    }

    return;

}

int Ask(int l,int r){

    int z=lg[r-l+1];

    return max(f[l][z],f[r-(1<<z)+1][z]);

}

int main()

{

    scanf("%s",t+1);m=strlen(t+1);

    scanf("%s",s+1);n=strlen(s+1);

    scanf("%d",&q);last=cnt=1;

    for(int i=1;i<=n;i++)Insert(s[i]-'a');

    for(int i=1,p=1,l=0;i<=m;i++){

        int c=t[i]-'a';

        while(!ch[p][c])p=fa[p],l=len[p];

        if(!p)p=1,l=0;

        else p=ch[p][c],l++;

        f[i][0]=l;

    }

    for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;

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

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

            f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);

    while(q--){

        int L,R;scanf("%d%d",&L,&R);

        int l=1,r=R-L+1;

        while(l<=r){

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

            if(Ask(L+mid-1,R)>=mid)l=mid+1;

            else r=mid-1;

        }

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

    }

    return 0;

}

巴特西

P6640-[BJOI2020]封印【SAM,二分】

正题

题目大意

解题思路

code

最新文章

热门文章