← 返回题目列表

AtCoder · abc329_e

H. 邮票

中文机器翻译题面 查看原题

分数: 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 通过如下操作。

  1. 替换 X[3:5] 与 T. X 变为 ##ABC##.
  2. 替换 X[1:3] 与 T. X 变为 ABCBC##.
  3. 替换 X[5:7] 与 T. X 变为 ABCBABC.

示例输入 2

7 3
ABBCABC
ABC

示例输出 2

No

无论你如何操作,都不可能使 X 匹配 S.


示例输入 3

12 2
XYXXYXXYYYXY
XY

示例输出 3

Yes