P6640 [BJOI2020] 封印

FxorG · 2021-07-07 19:11:22 · 个人记录

\text{Solution}

考虑子串是字符串前缀的后缀，那么我们可以预处理出 f[i] 表示 s 字符串的 [1,i] 能在t中匹配成功 [i-f[i]+1,i]。

我们可以用对t建立 SAM，跳下 father 就好。

那么答案就是：

但这样单次 O(n)。

假如 f[i] \leq i-l+1，得 i+1-f[i] \geq x。

考虑 i 单增，f[i] 要么匹配成功就从 f[i-1]+1，要么全部失败清0，那么 i+1-f[i] 单调不降。

二分出一个 pos，使得 [l,pos-1] 满足 f[i] \ge i-l+1， [pos,r] 满足 f[i] \le i-l+1。

然后我们在 [pos,r] 中找 \max \{f[i] \} 即可。

\text{Code}

// 前缀的后缀匹配度，就你每次相当于往后面拼一个 
#include <bits/stdc++.h>

#define N (int)(5e5+5)

using namespace std;

char s[N],t[N];
int LOG[N],len[N],f[N],ST[22][N],fa[N],son[26][N];
int n,m,tot=1,las=1;

void ins(int c) {
    int pre=las,x=++tot; las=x; len[x]=len[pre]+1;
    for(;pre&&!son[c][pre];pre=fa[pre]) son[c][pre]=x;
    int y=son[c][pre];
    if(!pre) fa[x]=1;
    else if(len[y]==len[pre]+1) fa[x]=y;
    else {
        int p=++tot; len[p]=len[pre]+1;
        fa[p]=fa[y]; fa[x]=fa[y]=p;
        for(int i=0;i<26;i++) son[i][p]=son[i][y];
        for(;pre&&son[c][pre]==y;pre=fa[pre]) son[c][pre]=p;
    }
}

void init() {
    LOG[0]=-1; for(int i=1;i<=n;i++) LOG[i]=LOG[(i>>1)]+1;
    for(int i=1;i<=n;i++) ST[0][i]=f[i];
    for(int j=1;j<=20;j++) {
        for(int i=1;i+(1<<j)-1<=n;i++) {
            ST[j][i]=max(ST[j-1][i],ST[j-1][i+(1<<(j-1))]);
        }
    }   
}

int query(int l,int r) {
    if(l>r) return 0;
    return max(ST[LOG[r-l+1]][l],ST[LOG[r-l+1]][r-(1<<LOG[r-l+1])+1]);
}

int main() {
    scanf("%s%s",s+1,t+1);
    n=strlen(s+1); m=strlen(t+1);   
    for(int i=1;i<=m;i++) ins(t[i]-'a');
    int qwq=0,p=1;
    for(int i=1;i<=n;i++) {
        int c=s[i]-'a';
        while(p!=1&&!son[c][p]) p=fa[p],qwq=len[p];
        if(son[c][p]) p=son[c][p],++qwq;
        f[i]=qwq;
    //  cout<<"i: "<<i<<" f[i]: "<<f[i]<<endl;
    }
    init();
    int q,x,y; scanf("%d",&q);
    for(int h=1;h<=q;h++) {
        scanf("%d%d",&x,&y);
        int l=x,r=y,res=r+1;
        while(l<=r) {
            int mid=(l+r)>>1;
            if(mid+1-f[mid]>=x) res=mid,r=mid-1;
            else l=mid+1;
        }
        printf("%d\n",max(res-x,query(res,y)));
    }
}
/*
min{f[i],i-x+1}

i-x+1单增
f[i]不一定单增

前移是最好的？ 

fi]: 2 1 1 2 3 
     1 2 3 4 5

    存在一个i使得  :f[i]<=i-x+1  x<=i+1-f[i] i+1-f[i]>=x
    考虑 i单调增 f[i]可+1 所以i+1-f[i]单调不降
     二分 对于[pos,y]取max{f[i]} 然后[x,pos-1]贡献为 pos-1-x+1=pos-x 
*/```