AT_abc329_e [ABC329E] Stamp 题解

题目翻译

给你两个字符串：\(S\) 由大写英文字母组成，长度为 \(N\)；\(T\) 也由大写英文字母组成，长度为 \(M\)，小于 \(N\)。有一个长度为 \(N\) 的字符串 \(X\)，它只由 # 字符组成。请判断是否有可能通过执行以下任意次数的操作使 \(X\) 与 \(S\) 匹配：在 \(X\) 中选择 \(M\) 个连续字符，并用 \(T\) 替换它们。

分析

问题一：我们什么时候能够替换？

按照样例来解释：

7 3
ABCBABC
ABC

可以看出，样例是放了三个 \(T\)。

在考虑 \(S\) 的其他情况。如果 \(S\) 为 ABBC 那么就是不可以的，因为无法用两个 \(T\) 来组成，因为两个字符串都会失去前缀和后缀。

在自己列举几种后发现：

两个 \(T\)，前者没有部分后缀或者后者没有部分前缀是可以相匹配的，但是呢，两个并存是不可以的。

问题二：怎么做呢？

我们可以使用 DP 的方式记录状态 \(dp_{i,j}\) 代表到第 \(i\) 个字符，此时位置是 \(T\) 中的下标几，然后表示能不能到达。

于是我们可以得到转移：当 \(dp_{i-1,j-1}\) 成立时，\(dp_{i,j}\) 和 \(dp_{i,1}\) 都成立，如果 \(dp_{i-1,m}\) 成立，那么对于所有的 \(j\)，都有 \(dp_{i,j}\) 成立。

然后再判断一下两个字符串是否相等，如果不相等，把他换回不成立。

AC code：

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define fir first
#define se second
#define endl '\n'
#define debug puts("AK IOI")
using namespace std;
const int N = 2e5+5;
int n,m;
string s,t;
bool dp[N][10];

int main(){
	cin >> n >> m;
	cin >> s >> t;
	s=' '+s;
	t=' '+t;
	if(s[1] == t[1])dp[1][1]=1;
	
	for(int i = 1;i <= n;i++){
		for(int j = 2;j <= m;j++)
			if(dp[i-1][j-1]) dp[i][j]=dp[i][1]=1;
		if(dp[i-1][m]) for(int j = 1;j <= m;j++)dp[i][j]=1;
		
		bool ac=0;
		for(int k = 1;k <= m;k++){
			if(t[k]==s[i] && dp[i][k]) ac=1;
			else if(dp[i][k]) dp[i][k] = 0;
		}if(ac==0){
			cout<<"No";	
			return 0;
		}
	}if(dp[n][m])cout<<"Yes";
	else cout<<"No";
	return 0;
}