「SWTR-05」String

Description

给定串 (S) 和 (T)，每次可以在 (T) 前或后拼接一个 (T) 的子串，求最小步数使得 (T) 变成 (S)。

Solution

暴力区间dp，剪剪枝有可以做到 50%，考场上没判 -1，怒丢 40pts。

考虑一个区间 ([l,r]) 能有的转移，假设其能转移到 ([l',r])，其中 (l'in [x,l))，那么实际上我们只需要保留 ([x,l]) 这个区间进行转移，也就是每次找最远的能转移的区间进行转移。考虑为什么是对的。大区间一定是包含小区间的所有子串的，而选择大区间还会使得剩下的串更小，不会使得答案更劣。那么现在的问题就是快速处理出一个区间最多能扩展到哪儿。类比于上面的道理，记一个区间 ([l,r]) 向右能扩展的最大长度为 (f_{l,r})，那么一定有 (f_{l,r}geq f_{l+1,r})，所以直接从 (f_{l+1,r}) 开始枚举，新增的能匹配的一定是以 (l) 为起点的串，可以用 Hash 扩展。

计算答案可以用 bfs，因为每次转移增量都是一。

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;

typedef long long ll;

const int Bs=233;
const int N=5e3+7;
const int Mod=998244353;

struct Seg{
    int l,r;
    Seg(int l_=0,int r_=0):l(l_),r(r_){}
};

queue<Seg> Q;
char s[N],t[N];
ll pw[N],hs=0,Hs[N];
int toL[N][N],toR[N][N],dp[N][N];

inline ll Get(int l,int r){
    return (Hs[r]-Hs[l-1]*pw[r-l+1]%Mod+Mod)%Mod;
}

int main(){
//    freopen("cutstring.in","r",stdin);
//    freopen("cutstring.out","w",stdout);
    scanf("%s%s",s+1,t+1);
    int n=strlen(s+1),m=strlen(t+1); pw[0]=1;
    for(int i=1;i<=n;i++)
        pw[i]=pw[i-1]*Bs%Mod,
        Hs[i]=(Hs[i-1]*Bs%Mod+s[i])%Mod;
    for(int i=1;i<=m;i++)
        hs=(hs*Bs%Mod+t[i])%Mod;
    for(int l=1;l<=n;l++){
        int ret=1;
        for(int r=l;r<=n;r++){
            while((l-ret>=1&&r-l+1>=ret)&&Get(r-ret+1,r)==Get(l-ret,l-1)) ret++;
            toL[l][r]=ret-1;
        }
    }
    for(int r=n;r;r--){
        int ret=1;
        for(int l=r;l;l--){
            while((r+ret<=n&&r-l+1>=ret)&&Get(l,l+ret-1)==Get(r+1,r+ret)) ret++;
            toR[l][r]=ret-1;
        }
    }
//    for(int i=1;i<=n;i++)
//        for(int j=i;j<=n;j++)
//            printf("%d %d %d %d
",i,j,toL[i][j],toR[i][j]);
    memset(dp,-1,sizeof(dp));
    for(int i=1;i<=n;i++)
        if(Get(i,i+m-1)==hs) Q.push(Seg(i,i+m-1)),dp[i][i+m-1]=0;
    while(!Q.empty()){
        Seg t=Q.front(); Q.pop();
    //    printf("%d %d %d
",t.l,t.r,dp[t.l][t.r]);
        if(toL[t.l][t.r]){
            const int del=toL[t.l][t.r];
            if(dp[t.l-del][t.r]==-1){
                dp[t.l-del][t.r]=dp[t.l][t.r]+1;
                Q.push(Seg(t.l-del,t.r));
            }
        }
        if(toR[t.l][t.r]){
            const int del=toR[t.l][t.r];
            if(dp[t.l][t.r+del]==-1){
                dp[t.l][t.r+del]=dp[t.l][t.r]+1;
                Q.push(Seg(t.l,t.r+del));
            }
        }
    }
    printf("%d",dp[1][n]);
}