题目翻译
给你两个字符串：\(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;
}