102592: [AtCoder]ABC259 C - XX to XXX
Description
Score : $300$ points
Problem Statement
You are given two strings $S$ and $T$. Determine whether it is possible to make $S$ equal $T$ by performing the following operation some number of times (possibly zero).
Between two consecutive equal characters in $S$, insert a character equal to these characters. That is, take the following three steps.
- Let $N$ be the current length of $S$, and $S = S_1S_2\ldots S_N$.
- Choose an integer $i$ between $1$ and $N-1$ (inclusive) such that $S_i = S_{i+1}$. (If there is no such $i$, do nothing and terminate the operation now, skipping step 3.)
- Insert a single copy of the character $S_i(= S_{i+1})$ between the $i$-th and $(i+1)$-th characters of $S$. Now, $S$ is a string of length $N+1$: $S_1S_2\ldots S_i S_i S_{i+1} \ldots S_N$.
Constraints
- Each of $S$ and $T$ is a string of length between $2$ and $2 \times 10^5$ (inclusive) consisting of lowercase English letters.
Input
Input is given from Standard Input in the following format:
$S$ $T$
Output
If it is possible to make $S$ equal $T$, print Yes
; otherwise, print No
.
Note that the judge is case-sensitive.
Sample Input 1
abbaac abbbbaaac
Sample Output 1
Yes
You can make $S =$ abbaac
equal $T =$ abbbbaaac
by the following three operations.
- First, insert
b
between the $2$-nd and $3$-rd characters of $S$. Now, $S =$abbbaac
. - Next, insert
b
again between the $2$-nd and $3$-rd characters of $S$. Now, $S =$abbbbaac
. - Lastly, insert
a
between the $6$-th and $7$-th characters of $S$. Now, $S =$abbbbaaac
.
Thus, Yes
should be printed.
Sample Input 2
xyzz xyyzz
Sample Output 2
No
No sequence of operations makes $S =$ xyzz
equal $T =$ xyyzz
.
Thus, No
should be printed.
Input
题意翻译
你有两个字符串 $S$ 和 $T$。对于 $S$ 每次操作可以在相邻两个相同字符之间插入一个相同字符,例如 baabb 可以通过一次操作变成 baaabb。 请问是否能通过若干次操作将字符串 $S$ 变成 $T$。 $S$ 和 $T$ 的长度在 $2$ 和 $2 \times 10^5$ 之间,且只包含小写字母。 如果可以,则输出 `Yes`,否则输出 `No`。 注意大小写。Output
问题描述
给你两个字符串$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$都是一个由小写英文字母组成的字符串,长度在$2$到$2 \times 10^5$(包括)之间。
输入
输入从标准输入按以下格式给出:
$S$ $T$
输出
如果可以使得$S$等于$T$,则打印Yes
;否则,打印No
。
注意判断是区分大小写的。
样例输入1
abbaac abbbbaaac
样例输出1
Yes
你可以通过以下三个操作使得$S =$ abbaac
等于$T =$ abbbbaaac
。
- 首先,在$S$的第$2$个字符和第$3$个字符之间插入字符
b
。现在,$S =$abbbaac
。 - 接下来,在$S$的第$2$个字符和第$3$个字符之间再次插入字符
b
。现在,$S =$abbbbaac
。 - 最后,在$S$的第$6$个字符和第$7$个字符之间插入字符
a
。现在,$S =$abbbbaaac
。
因此,应该打印Yes
。
样例输入2
xyzz xyyzz
样例输出2
No
没有一系列操作使得$S =$ xyzz
等于$T =$ xyyzz
。
因此,应该打印No
。