AtCoder Beginner Contest 329
比赛地址:Sky Inc, Programming Contest 2023(AtCoder Beginner Contest 329) - AtCoder
E - Stamp
Problem Statement
You are given two strings: S S S, which consists of uppercase English letters and has length N N N, and T T T, which also consists of uppercase English letters and has length M ( ≤ N ) M\ (\leq N) M (≤N).
There is a string
X
X
X of length
N
N
N consisting only of the character #
. Determine whether it is possible to make
X
X
X match
S
S
S by performing the following operation any number of times:
- Choose M M M consecutive characters in X X X and replace them with T T T.
Constraints
- 1 ≤ N ≤ 2 × 1 0 5 1 \leq N \leq 2\times 10^5 1≤N≤2×105
- 1 ≤ M ≤ min ( N , 1 \leq M \leq \min(N, 1≤M≤min(N, 5 5 5 ) ) )
- S S S is a string consisting of uppercase English letters with length N N N.
- T T T is a string consisting of uppercase English letters with length M M M.
Input
The input is given from Standard Input in the following format:
N N N M M M
S S S
T T T
Output
Print Yes
if it is possible to make
X
X
X match
S
S
S; print No
otherwise.
Sample Input 1
7 3
ABCBABC
ABC
Sample Output 1
Yes
Below, let X [ l : r ] X[l:r] X[l:r] denote the part from the l l l-th through the r r r-th character of X X X.
You can make X X X match S S S by operating as follows.
- Replace
X
[
3
:
5
]
X[3:5]
X[3:5] with
T
T
T.
X
X
X becomes
##ABC##
. - Replace
X
[
1
:
3
]
X[1:3]
X[1:3] with
T
T
T.
X
X
X becomes
ABCBC##
. - Replace
X
[
5
:
7
]
X[5:7]
X[5:7] with
T
T
T.
X
X
X becomes
ABCBABC
.
题目大意
给定两个字符串 S 1 , S 2 S_1,S_2 S1,S2,长度分别为 n , m n,m n,m,然后再给一个长度为 n n n的字符串 S 3 S_3 S3, S 3 S_3 S3是全部由‘#’组成的字符串。
题目要求每次用 S 2 S_2 S2来覆盖 S 3 S_3 S3的一段连续的位置,判断是否可以将 S 3 S_3 S3构造成 S 1 S_1 S1。
思路
我们可以将本题理解为粘胶带,我们可以将 S 3 S_3 S3看作是一个长度为 n n n空白的板子,将 S 2 S_2 S2看作是一个长度为 m m m且印有字母的胶带,这样每次操作就相当于在空白板子上粘胶带,而每次粘胶带时都会覆盖掉当前这段长度为 m m m的位置,求最后是否能将该空白的板子粘成 S 1 S_1 S1的样子。
如果我们考虑根据粘胶带的顺序来判断是否能构造成 S 1 S_1 S1,那么就会出现有后效性,即后续操作会影响当前操作。
于是换个思路来想,根据粘胶带的思路,无论怎么粘,最后一个粘的胶带都不会被遮挡,所以我们考虑倒着操作,将 S 1 S_1 S1胶带一张一张揭下来,最后判断是否能揭成一个空白的板子。
因此我们枚举 S 1 S_1 S1中的子段 S 2 S_2 S2,当然其中包含形如“AB#”,这种与“ABC”等价,因为第三个位置实际上是会被覆盖的。然后用dfs一层一层的揭,在dfs搜索的时候要注意,当前位置的前面和后面都要搜索一边,因为这个字符串可能被覆盖的前缀,也可能是后缀。
实现
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
#define LL long long
#define ULL unsigned long long
#define PII pair<int, int>
#define lowbit(x) (x & -x)
#define Mid ((l + r) >> 1)
#define ALL(x) x.begin(), x.end()
#define endl '\n'
#define fi first
#define se second
const int INF = 0x7fffffff;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int n, m;
string s1, s2;
void modify(int x) {
for(int i = x; i <= x + m - 1; i ++ ) {
s1[i] = '#';
}
}
bool check(int x) {
bool flag = false;
for(int i = 0; i < m; i ++ ) {
if(s1[x + i] != s2[i]) {
if(s1[x + i] != '#')
return false;
} else {
flag = true; //不能全为'#'
}
}
return flag;
}
void dfs(int x) {
modify(x);
for(int i = x + 1; i < x + m && i < n; i ++ ) {
if(check(i)) dfs(i);
}
for(int i = max(0, x - m + 1); i < x; i ++ ) {
if(check(i)) dfs(i);
}
}
void Solved() {
cin >> n >> m;
cin >> s1 >> s2;
for(int i = 0; i < n - m + 1; i ++ ) {
if(check(i)) dfs(i);
}
for(int i = 0; i < n; i ++ ) {
if(s1[i] != '#') {
cout << "No" << endl; return;
}
}
cout << "Yes" << endl;
}
signed main(void) {
IOS
int ALL = 1;
// cin >> ALL;
while(ALL -- ) Solved();
return 0;
}