/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
英小文字からなる 2 つの文字列 S, T が与えられます。 次の操作を好きな回数（ 0 回でも良い）行うことで、S を T と一致させることができるかを判定してください。
S において同じ文字が 2 文字連続しているところの間に、その文字と同じ文字を 1 つ挿入する。 すなわち、下記の 3 つの手順からなる操作を行う。
- 現在の S の長さを N とし、S = S_1S_2\ldots S_N とする。
- 1 以上 N-1 以下の整数 i であって、S_i = S_{i+1} を満たすものを 1 つ選択する。（ただし、そのような i が存在しない場合は、何もせずに手順 3.をスキップして操作を終了する。）
- S の i 文字目と i+1 文字目の間に文字 S_i(= S_{i+1}) を 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
下記の 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
xyzz xyyzz
出力例 2
No
どのように操作を行っても、 S = xyzz を T = xyyzz に一致させることはできません。
よって、No を出力します。
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
bbetween the 2-nd and 3-rd characters of S. Now, S =abbbaac. - Next, insert
bagain between the 2-nd and 3-rd characters of S. Now, S =abbbbaac. - Lastly, insert
abetween 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.