Stamp

题目描述

给定两个字符串：$S$，由大写英文字母组成，长度为 $N$，以及 $T$，也由大写英文字母组成，长度为 $M\ (\leq N)$。 有一个长度为 $N$ 且仅由字符 # 组成的字符串 $X$。判断是否可以通过任意次数执行以下操作使 $X$ 与 $S$ 匹配：

选择 $X$ 中的 $M$ 个连续字符并将它们替换为 $T$。

输入格式

输入从标准输入按以下格式给出： $N$ $M$ $S$ $T$

输出格式

如果可以使 $X$ 与 $S$ 匹配则输出 $Yes$；否则输出 $No$。

7 3
ABCBABC
ABC

Yes

7 3
ABBCABC
ABC

No

12 2
XYXXYXXYYYXY
XY

Yes

提示

$1 \leq N \leq 2\times 10^5$ $1 \leq M \leq \min(N,$ $5$$)$ $S$ 是一个由大写英文字母组成的长度为 $N$ 的字符串。 $T$ 是一个由大写英文字母组成的长度为 $M$ 的字符串。下面，令 $X[l:r]$ 表示 $X$ 的第 $l$ 个到第 $r$ 个字符的部分。 可以通过如下操作使 $X$ 与 $S$ 匹配。

将 $X[3:5]$ 替换为 $T$。此时 $X$ 变为 $##ABC##$。 将 $X[1:3]$ 替换为 $T$。此时 $X$ 变为 $ABCBC##$。 将 $X[5:7]$ 替换为 $T$。此时 $X$ 变为 $ABCBABC$。

无论如何操作，都不可能使 $X$ 与 $S$ 匹配。

标签: AtCoder|abc329E

来源

AtCoder|abc329E