题解洛谷 P6640 【[BJOI2020] 封印】

设\(lenth_i\)为\(s\)在\(i\)位置的前缀的后缀为\(t\)的一个子串的最长长度，即为从\(i\)位置开始往前和\(t\)的最长公共子串长度。其可以通过对\(t\)建后缀自动机，然后让\(s\)在自动机上匹配来求出。

求出\(lenth_i\)后，对于区间\([l,r]\)的一个询问，其答案即为：

\[ \max_{i=l}^r \lbrace\ \min(lenth_i,i-l+1)\ \rbrace
\]

发现内层的\(\min\)不好处理，考虑将其去掉：

当\(lenth_i \leqslant i-l+1\)时，其值为\(lenth_i\)，转化得\(i-lenth_i+1 \geqslant l\)，发现\(i-lenth_i+1\)的值是单调不降的，因为每到下一个位置，\(i\)都会加一，而\(lenth_i\)可能加一，可能清零，所以该值是单调不降的。

那么对于区间\([l,r]\)，一定存在一个位置\(pos\)，满足所有\(i \geqslant pos\)，都有\(i-lenth_i+1 \geqslant l\)。那么在区间\([pos,r]\)中，\(\min\)取到了\(lenth_i\)，在区间\([l,pos-1]\)中，\(\min\)取到了\(i-l+1\)。

\(pos\)可以通过二分求得，然后答案即为区间\([pos,r]\)内\(lenth_i\)的最大值和\(pos-l\)取\(\max\)。

\(code:\)

#include<bits/stdc++.h>

#define maxn 400010

using namespace std;

template<typename T> inline void read(T &x)

{

    x=0;char c=getchar();bool flag=false;

    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}

    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}

    if(flag)x=-x;

}

int l1,l2,q,root=1,las=1,tot=1;

int len[maxn],fa[maxn],ch[maxn][2],lenth[maxn],f[maxn][25],lg[maxn];

char s[maxn],t[maxn];

void insert(int c)

{

    int p=las,np=las=++tot;

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

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

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

    else

    {

        int q=ch[p][c];

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

        else

        {

            int nq=++tot;

            ch[nq][0]=ch[q][0],ch[nq][1]=ch[q][1];

            len[nq]=len[p]+1,fa[nq]=fa[q],fa[q]=fa[np]=nq;

            while(ch[p][c]==q) ch[p][c]=nq,p=fa[p];

        }

    }

}

void init()

{

    lg[0]=-1;

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

    for(int i=1;i<=l1;++i) f[i][0]=lenth[i];

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

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

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

}

int query(int l,int r)

{

    if(l>r) return 0;

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

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

}

int find(int l,int r)

{

    int pos=r+1,L=l;

    while(l<=r)

    {

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

        if(mid-lenth[mid]+1>=L) pos=mid,r=mid-1;

        else l=mid+1;

    }

    return pos;

}

void work()

{

    int p=root;

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

    {

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

        if(ch[p][c]) lenth[i]=lenth[i-1]+1,p=ch[p][c];

        else

        {

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

            if(!p) p=root;

            else lenth[i]=len[p]+1,p=ch[p][c];

        }

    }

}

int main()

{

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

    l1=strlen(s+1),l2=strlen(t+1);

    for(int i=1;i<=l2;++i) insert(t[i]-'a');

    work(),init(),read(q);

    while(q--)

    {

        int l,r,pos;

        read(l),read(r),pos=find(l,r);

        printf("%d\n",max(query(pos,r),pos-l));

    }

    return 0;

}

巴特西

题解洛谷 P6640 【[BJOI2020] 封印】

最新文章

热门文章

巴特西

题解 洛谷 P6640 【[BJOI2020] 封印】

最新文章

热门文章

题解洛谷 P6640 【[BJOI2020] 封印】