XX to XXX

题目描述

你得到两个字符串 $S$ 和 $T$。 判断是否可以通过若干次（可能为零次）下面的操作使 $S$ 等于 $T$。

在 $S$ 中两个相邻且相等的字符之间插入一个等于这些字符的字符。 也就是说，执行以下三个步骤。

让 $N$ 为当前 $S$ 的长度，且 $S = S_1S_2\ldots S_N$。 选择一个整数 $i$ 在 $1$ 到 $N-1$（包含端点）之间，满足 $S_i = S_{i+1}$。 （如果不存在这样的 $i$，则什么也不做并立即终止操作，跳过步骤 3。） 在 $S$ 的第 $i$ 个和第 $i+1$ 个字符之间插入一个字符的单个拷贝 $S_i(= S_{i+1})$。现在，$S$ 的长度为 $N+1$：$S_1S_2\ldots S_i S_i S_{i+1} \ldots S_N$。

输入格式

输入按标准输入给出，格式如下： $S$ $T$

输出格式

如果可以使 $S$ 等于 $T$，则输出 $Yes$；否则，输出 $No$。 注意评测为区分大小写。

abbaac
abbbbaaac

Yes

xyzz
xyyzz

No

提示

每个 $S$ 和 $T$ 的长度在 $2$ 到 $2 \times 10^5$（包含端点）之间，由小写英文字母组成。你可以通过以下三次操作将 $S =$ $abbaac$ 变为 $T =$ $abbbbaaac$。

首先，在 $S$ 的第 $2$ 和第 $3$ 个字符之间插入 $b$。现在，$S =$ $abbbaac$。 接着，再次在 $S$ 的第 $2$ 和第 $3$ 个字符之间插入 $b$。现在，$S =$ $abbbbaac$。 最后，在 $S$ 的第 $6$ 和第 $7$ 个字符之间插入 $a$。现在，$S =$ $abbbbaaac$。

因此，应输出 $Yes$。
没有任何操作序列可以将 $S =$ $xyzz$ 变为 $T =$ $xyyzz$。 因此，应输出 $No$。

标签: AtCoder|abc259C

来源

AtCoder|abc259C