本文主要是介绍AtCoder Beginner Contest 329 E - Stamp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接
题目大意：给你两个字符串：S 由大写英文字母组成，长度为 N；
T 也由大写英文字母组成，长度为 M (≤N)。
有一个长度为 N 的字符串 X 仅由字符 '#' 组成。
请判断是否有可能通过执行以下任意次数的操作使 X 与 S 匹配：
在 X 中选择连续的 M 个字符，并用 T 代替。
检查s中每一个下标p，视为用t替换的左端点，查看s(p, p + m - 1)与t是否相同，
如果相同是不是就意味着s这一段内可以覆盖掉原来的字符，我们把可以覆盖的标记为'#'，那么以前该字符的取值就不重要了，再检查[p - m + 1, p + m - 1]这个范围（p能覆盖可以影响到的范围）的每一个下标，考虑除'#'外的字符与t中的是否相同。最终s中字符都为'#'即为Yes。
#include <bits/stdc++.h>
#define SQR(x) fixed << setprecision(x)
using namespace std;using ll = long long;int n, m;
bool vis[N]; //标记每一个下标是否搜索过
string s, t;void dfs(int p) {if(p < 0 || p + m - 1 >= n || vis[p]) return; for (int i = 0; i < m; i++) { //匹配if(s[p + i] == '#') continue; if(s[p + i] != t[i]) return; }vis[p] = true;for (int i = 0; i < m; i++) { //匹配成功s[p + i] = '#';}for (int i = p - m + 1; i <= p + m - 1; i++) { //再搜索可以影响的范围dfs(i);}
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n >> m;cin >> s >> t;for (int i = 0; i < n; i++) {dfs(i);}for (int i = 0; i < n; i++) {if(s[i] != '#') {cout << "No\n";return 0;}}cout << "Yes\n";return 0;
}
这篇关于AtCoder Beginner Contest 329 E - Stamp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
