题解 P5479 【[BJOI2015]隐身术】

· · 题解

先\%一下神仙的dp做法

这题一看n+m≤10^5，就知道要合并起来了(大雾

再看k≤5，那就只用直接DFS枚举操作方案

记录在字符串A的匹配位置x和在字符串B的匹配位置y

还要记录剩余操作数判断是否终止

每次跳掉两个后缀的lcp（也就是最长前缀）

目前跳到的地方一定是不相同的字符

也就是A[x] \ne B[y]

必然进行一次操作

插入：在A[x]前面插入一个和B[y]一样的字符，x的位置不变，y往后一个

删除：将A[x]删去，x向后一个

修改：将A[x]的字符改为B[y]的字符，x,y均往后一个

每次某个串匹配到结尾时，B中的某个区间的前缀都会合法，注意到这些合法的前缀长度与A长度相差一定不超过k，于是用一个2*k+1的差分数组记录答案即可

每次DFS由于转移时一定会增加一次操作数，所以最多递归k次，最差复杂度为O(3^k)

所以总复杂度为O(n\log n+n3^k)

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define int long long
const int M=1e5+5;

int n,m=125,ans=0,k,sl,tl,L,R,now,pre[M];
int tx[M],tp[M],sa[M],rk[M],height[M];
int st[M][35],log[M];
char r[M],s[M],t[M];

void jsort(){
    for(int i=0;i<=m;i++) tx[i]=0;
    for(int i=1;i<=n;i++) tx[rk[i]]++;
    for(int i=1;i<=m;i++) tx[i]+=tx[i-1];
    for(int i=n;i>=1;i--) sa[tx[rk[tp[i]]]--]=tp[i];
}

void Build_SA(){//板子 
    jsort();//O(n)的基排 
    for(int w=1,p=0;p<n;m=p,w<<=1){
        p=0;
        for(int i=1;i<=w;i++) tp[++p]=n-w+i;
        for(int i=1;i<=n;i++) if(sa[i]>w) tp[++p]=sa[i]-w;
        jsort();
        std::swap(tp,rk);
        rk[sa[1]]=p=1;
        for(int i=2;i<=n;i++){
            if(tp[sa[i-1]]==tp[sa[i]]&&tp[sa[i-1]+w]==tp[sa[i]+w]) rk[sa[i]]=p;
            else rk[sa[i]]=++p;
        }
    }
    for(int i=1;i<=n;i++) sa[i-1]=sa[i]-1;//将SA给变为0-(n-1) 
}

void Build_Height(){//求height 
    for(int i=0;i<n;i++) rk[sa[i]]=i;
    int k=0;
    for(int i=0;i<n;i++){
        if(!rk[i]) continue;
        if(k) k--;
        int j=sa[rk[i]-1];
        while(r[i+k]==r[j+k]) k++;
        height[rk[i]]=k;
    }
}

void Build_ST(){//st表优化求lcp 
    for(int i=2;i<=n;i++) log[i]=log[i>>1]+1;
    for(int i=0;i<n;i++) st[i][0]=height[i];
    for(int j=1;j<=25;++j){
        for(int i=0;i+(1<<j)-1<n;i++){
            st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
        }
    }
}

int Query(int l,int r){//O(1)查询两个字符串分别的后缀l和后缀r的lcp的长度
    int k=log[r-l+1];
    return min(st[l][k],st[r-(1<<k)+1][k]);
}

void DFS(int x,int y,int z){//爆搜，x代表在字符串A的匹配位置，y代表在字符串B的匹配位置，z代表剩余操作数 
    if(z>k) return ;
    int l=rk[x],r=rk[y];
    if(l>r) swap(l,r);
    int lcp=Query(l+1,r);
    x+=lcp,y+=lcp;//跳过相同的字符串 
    if(x==sl||y==n){
        int d=k-z-(sl-x);
        if(d<0) return ;
        int l=max(y-1-d,now),r=min(y-1+d,n-1);
        L=min(l,L),R=max(r+1,R);
        pre[l]++,pre[r+1]--;
        return ;
    }
    DFS(x+1,y,z+1),DFS(x,y+1,z+1),DFS(x+1,y+1,z+1);//三种状态转移 
}

signed main(){
    scanf("%lld%s%s",&k,s,t);
    sl=strlen(s),tl=strlen(t);
    for(int i=0;i<sl;i++) r[n++]=s[i];r[n++]='#';//分开前后字符串 
    for(int i=0;i<tl;i++) r[n++]=t[i];
    for(int i=1;i<=n;i++) rk[i]=r[i-1],tp[i]=i;
    Build_SA(),Build_Height(),Build_ST();
    for(int i=0;i<tl;i++){
        now=sl+i+1,L=n-1,R=0;
        DFS(0,sl+i+1,0);
        for(int j=L;j<=R;++j) ans+=(pre[j]+=pre[j-1])>0;
        for(int j=L;j<=R;++j) pre[j]=0;
    }
    printf("%lld\n",ans);
}