自动搬运

查看原文

来自洛谷，原作者为

	lhm_ sjzez 的一名 OI 学生

搬运于2025-08-24 22:22:40，当前版本为作者最后更新于2020-06-28 20:14:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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