← 返回题目列表

Codeforces · 1975/G

G. Zimpha 粉丝俱乐部

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

有一天,Zimpha 无意中想到了一个问题。作为“Zimpha 粉丝俱乐部”的成员,你决定解决这个问题。

给定两个字符串 $$$s$$$ 和 $$$t$$$,长度分别为 $$$n$$$ 和 $$$m$$$。两个字符串均仅由小写英文字母 - 和 * 组成。

您需要替换所有出现的 * 和 -,并遵守以下规则:

- 对于每个 -,您必须将其替换为任何小写英文字母。
- 对于每个 *,您必须将其替换为仅由小写英文字母组成的任意(可能为零)长度的字符串。

请注意,您可以将两个不同的 - 实例替换为不同的字符。您还可以将 * 的两个不同实例替换为不同的字符串。

假设 $$$s$$$ 和 $$$t$$$ 已转换为 $$$s'$$$ 和 $$$t'$$$。现在您想知道是否有替代品可以使 $$$s'=t'$$$。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n, m \leq 2 \cdot 10^6$$$) - 分别是字符串 $$$s$$$ 和 $$$t$$$ 的长度。

第二行包含长度为 $$$n$$$ 的字符串 $$$s$$$。保证$$$s$$$仅由小写英文字母、-和*组成。

第三行包含长度为 $$$m$$$ 的字符串 $$$t$$$。保证$$$t$$$仅由小写英文字母、-和*组成。

输出

对于每个测试用例,如果存在使 $$$s'=t'$$$ 的替换,则输出“Yes”,否则输出“No”。

在任何情况下都可以输出“Yes”和“No”(例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应)。

示例

输入 #1

10 10
justmonika
j-stsayori

输出 #1

No

输入 #2

7 8
ttk-wxx
*tt-l-xx

输出 #2

Yes

输入 #3

13 11
asoulwangziji
-soulg*z-y-

输出 #3

No

输入#4

7 3
abc*cba
a*c

输出#4

No

输入 #5

20 18
bulijiojio-dibuliduo
*li*ji-*ox*i*-du*-

输出 #5

Yes

注意

在第二个测试用例中,我们可以将两个字符串转换为 ttklwxx。在 $$$s$$$ 中,- 将替换为 l。在 $$$t$$$ 中,* 将被空字符串替换,第一个和第二个 - 将分别替换为 k 和 w。

在第五个测试用例中,我们可以将两个字符串都转换为 bulijiojioxdibuliduo。