分数: 475 点
问题陈述
给你两个字符串: S,由大写英文字母组成,长度为 N,和 T,同样由大写英文字母组成,长度为 M\ (\leq N).
有一个字符串 X 长度 N 仅由字符组成 #。判断是否可以制作 X 匹配 S 通过执行以下操作任意多次:
- 选择 M 中的连续字符 X 并将其替换为 T.
约束
- 1 \leq N \leq 2\times 10^5
- 1 \leq M \leq \min(N, 5)
- S 是由大写英文字母组成的字符串,长度为 N.
- T 是由大写英文字母组成的字符串,长度为 M.
输入
输入由标准输入按以下格式给出:
N M S T
输出
打印 Yes 如果可以的话 X 匹配 S;打印 No 否则。
示例输入 1
7 3 ABCBABC ABC
示例输出 1
Yes
下面,让 X[l:r] 表示来自 l-th 通过 r第一个字符 X.
你可以使 X 匹配 S 通过如下操作。
- 替换 X[3:5] 与 T. X 变为
##ABC##. - 替换 X[1:3] 与 T. X 变为
ABCBC##. - 替换 X[5:7] 与 T. X 变为
ABCBABC.
示例输入 2
7 3 ABBCABC ABC
示例输出 2
No
无论你如何操作,都不可能使 X 匹配 S.
示例输入 3
12 2 XYXXYXXYYYXY XY
示例输出 3
Yes