Text Editor

题目传送门

题目大意

给出两个字符串 $a$ 和 $s$ ，长度分别为 $n$ 和 $m$ ，且 $1≤m≤n≤5000$ ，问经过最少多少次操作能从 $a$ 串变成 $s$ 串，如果不能输出 $-1$ 。初始时光标位于 $a$ 串末尾。有几种操作

“left”，光标向前移动一格
“right”，光标向后移动一格
“home”，光标移动到最前面
“end”，光标移动到最后面
“backspace”，删除

思路

考虑每一个公共子串，这个公共子串的右边使用 backspace 直到该公共子串的右侧，而左侧使用 home 先移到最左边，再进行 right 和 backspace 操作，直到该公共子串的左侧。

以此遍历每一个公共子串，每次更新 $ans$ 的值，取 $min$ ，由此得到的最终结果即为所求，相当于是一个 $n^2$ 的 $dp$ 。当然，$ans$ 的值首先要初始化为一路从右到左 backspace 的操作数。

然而，要进行这样的操作，需要知道这个公共子串的左侧能不能满足题目要求，即左侧剩余的字符串能否互相匹配上，右侧同理，因此，我们还需要维护两个数组 $pre[i]$ 和 $suf[i]$ 分别表示在从左到右和从右到左的顺序下，首先能匹配上的下标。

代码

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<set>
#include<map>
#include<cmath>
#include<iostream>
#include<unordered_set>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define Inf 0x3f3f3f3f
//#define int long long
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
typedef pair<P,int> PP;
const int MAXX=5005;
const double eps=0.0000001;
const LL mod=1000000007;

int n,m,pre[MAXX],suf[MAXX];
char a[MAXX],s[MAXX];
int len[MAXX][MAXX];

inline void solve_it(){
	scanf("%d%d",&n,&m);
	getchar();scanf("%s",a+1);
	getchar();scanf("%s",s+1);
	bool flag=false;
	int first=0;
	for(int i=1,j=1;i<=n;++i){
		if(a[i]==s[j]){
			pre[j]=i;
			++j;
		}
		else if(!first)
			first=i;
		if(j>m)
			flag=true;
	}
	if(!flag){
		printf("-1\n");
		return;
	}
	if(n==m){
		printf("0\n");
		return;
	}
	for(int i=n,j=m;i>=1;--i){
		if(a[i]==s[j]){
			suf[j]=i;
			--j;
		}
		if(j==0)
			break;
	}
	
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			len[i][j]=((a[i]==s[j])?(len[i-1][j-1]+1):(0));
	int n1=n+1,m1=m+1;
	for(int i=1;i<=n1;++i)
		len[i][m1]=0;
	for(int i=1;i<=m1;++i)
		len[n1][i]=0;
	
	int ans=n-first+1;
	for(int j=1;j<=m;++j)
		for(int i=pre[i];i<=n;++i){
			if(len[i+1][j+1]) continue;
			int lenn=len[i][j];
			if((j==m||suf[j+1]>i)&&(j-lenn==0||pre[j-lenn]<i-lenn)){
				int jj=n-i;
				if(i>j)
					jj+=i-j+i-lenn+1;
				ans=min(ans,jj);
			}
		}
	
	printf("%d\n",ans);
}

signed main(){
	LL T;scanf("%lld",&T);
	while(T--)
		solve_it();
	
	return 0;
}