[ABC329E] Stamp 题解

正难则反。

直接往上覆盖不好做，那么可以考虑把字符从 \(S\) 上往下删。删的过程就是在 \(S\) 中找 \(T\) 并把他们变成 #。如果 \(S\) 中有字符为 #，那我们可以把它看成任意字符，因为向上贴的过程中有重复覆盖的情况，在删的时候我们并不知道他是否重复了，所以当成任意字符来看即可（这也是正着做困难的原因，不好处理覆盖的情况）。

实现的话先在 \(S\) 中找到 \(T\),然后向前回溯 \(m\) 位，因为有可能这段字符变为 # 后前面又能出现一次 \(T\)。dfs 即可。

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m;
char s[200005],t[200005];
bool check(int x){
	bool f=0;
	for(int i=x;i<=x+m-1;++i)
		if(s[i]!='#'){
			if(s[i]!=t[i-x+1])return 0;
			f=1;
		}
	if(f)for(int i=x;i<=x+m-1;++i)s[i]='#';//特判全为 # 的情况
	return f;
}
void dfs(int x){
	for(int i=x-1;i>=max(1,x-m+1);--i)if(check(i))dfs(i);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	cin>>(s+1)>>(t+1);
	for(int i=1;i<=n-m+1;++i)if(check(i))dfs(i);
	for(int i=1;i<=n;++i)if(s[i]!='#')return cout<<"No",0;
	cout<<"Yes";
	return 0;
}