题解 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。

$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;
}