AT_abc259_c [ABC259C] XX to XXX

题目描述

给定两个由小写英文字母组成的字符串 $S$ 和 $T$。请判断是否可以通过任意次数（可以为 $0$ 次）的如下操作，将 $S$ 变为 $T$。

在 $S$ 中，任选一处有两个相同字符连续出现的位置，在这两个字符之间插入一个相同的字符。即，操作包含以下三个步骤：

1. 设当前 $S$ 的长度为 $N$，记 $S = S_1S_2\ldots S_N$。
2. 选择一个满足 $1 \leq i \leq N-1$ 且 $S_i = S_{i+1}$ 的整数 $i$。（如果不存在这样的 $i$，则跳过步骤 3，操作结束。）
3. 在 $S$ 的第 $i$ 个字符和第 $i+1$ 个字符之间插入一个字符 $S_i(=S_{i+1})$。操作后，$S$ 变为长度为 $N+1$ 的字符串 $S_1S_2\ldots S_iS_iS_{i+1}\ldots S_N$。

输入格式

输入以以下格式从标准输入读入。

$S$ $T$

输出格式

如果可以将 $S$ 变为 $T$，输出 Yes；否则输出 No。请注意，判题时严格区分大小写。

输入输出样例 #1

输入 #1

abbaac
abbbbaaac

输出 #1

Yes

输入输出样例 #2

输入 #2

xyzz
xyyzz

输出 #2

No

说明/提示

限制条件

• $S$ 和 $T$ 均为长度在 $2$ 到 $2 \times 10^5$ 之间的仅包含小写英文字母的字符串。

样例解释 1

通过以下 $3$ 次操作，可以将 $S =$ abbaac 变为 $T =$ abbbbaaac。

• 首先，在 $S$ 的第 $2$ 个和第 $3$ 个字符之间插入 b，得到 $S =$ abbbaac。
• 接着，再次在 $S$ 的第 $2$ 个和第 $3$ 个字符之间插入 b，得到 $S =$ abbbbaac。
• 最后，在 $S$ 的第 $6$ 个和第 $7$ 个字符之间插入 a，得到 $S =$ abbbbaaac。 因此，输出 Yes。

样例解释 2

无论如何操作，都无法将 $S =$ xyzz 变为 $T =$ xyyzz。因此，输出 No。

由 ChatGPT 4.1 翻译