AT_abc329_e [ABC329E] Stamp

题目描述

给定一个由大写英文字母组成、长度为 $N$ 的字符串 $S$，以及一个由大写英文字母组成、长度为 $M\ (\leq N)$ 的字符串 $T$。

还有一个长度为 $N$、仅由 # 组成的字符串 $X$。你可以进行任意次数如下操作：

• 从 $X$ 中选择连续的 $M$ 个字符，并用 $T$ 替换它们。

请判断是否可以通过若干次操作将 $X$ 变为 $S$。

输入格式

输入通过标准输入按以下格式给出。

$N$ $M$
$S$
$T$

输出格式

如果可以将 $X$ 变为 $S$，输出 Yes，否则输出 No。

输入输出样例 #1

输入 #1

7 3
ABCBABC
ABC

输出 #1

Yes

输入输出样例 #2

输入 #2

7 3
ABBCABC
ABC

输出 #2

No

输入输出样例 #3

输入 #3

12 2
XYXXYXXYYYXY
XY

输出 #3

Yes

说明/提示

限制条件

• $1 \leq N \leq 2\times 10^5$
• $1 \leq M \leq \min(N, 5)$
• $S$ 是长度为 $N$ 的大写英文字母字符串。
• $T$ 是长度为 $M$ 的大写英文字母字符串。

样例解释 1

记 $X$ 的第 $l$ 个字符到第 $r$ 个字符的子串为 $X[l:r]$。可以按如下方式操作，将 $X$ 变为 $S$：

1. 用 $T$ 替换 $X[3:5]$，此时 X = ##ABC##。
2. 用 $T$ 替换 $X[1:3]$，此时 X = ABCBC##。
3. 用 $T$ 替换 $X[5:7]$，此时 $X = ABCBABC$。

样例解释 2

无论如何操作，都无法将 $X$ 变为 $S$。

由 ChatGPT 4.1 翻译