M - 挿入と削除 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

問題文

文字列 S, T, U が与えられます。 S, T は英小文字 (a–z) からなる文字列であり、U は A , B からなる文字列です。

S に対して i = 1, \dots, |U| の順に以下の操作を行うことで、S を T に一致させることが可能かどうかを判定してください。

  • U_i が A の場合、S の任意の位置に任意の英小文字を 1 文字挿入する。
  • U_i が B かつその時点で S が空文字列でない場合、S から任意に 1 文字選んで削除する。
  • U_i が B かつその時点で S が空文字列である場合、何もしない。

C 個のテストケースが与えられるので、それぞれについて解いてください。

制約

  • C は整数
  • 1 \leq C \leq 5\,000
  • S, T は英小文字 (a–z) からなる文字列
  • 1 \leq |S| \leq 5\,000
  • 1 \leq |T| \leq 5\,000
  • U は A, B からなる文字列
  • 1 \leq |U| \leq 5\,000
  • 各入力ファイルについて、すべてのテストケースの \max(|S|, |T|, |U|) の総和は 5\,000 以下である。

入力

入力は以下の形式で標準入力から与えられる。

C
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_C

\mathrm{case}_i は i 番目のテストケースを表す。各テストケースは以下の形式で与えられる。

S
T
U

出力

C 行出力せよ。

i 行目には、i 番目のテストケースにおいて S を T に一致させることが可能ならば Yes を、可能でないならば No を出力せよ。

入力例 1

4
cue
cube
A
club
cube
AB
crab
cube
AB
s
t
BBA

出力例 1

Yes
Yes
No
Yes

1 番目のテストケースにおいて、S は cue です。これに対して次のように操作を行うことで、S を T に一致させることが可能です。

  1. U_1 は A である。S の 2 文字目の直後に b を挿入することで、S は cube になる。

2 番目のテストケースにおいて、S は club です。これに対して次のように操作を行うことで、S を T に一致させることが可能です。

  1. U_1 は A である。S の 4 文字目の直後に e を挿入することで、S は clube になる。
  2. U_2 は B である。S の 2 文字目を削除することで、S は cube になる。

3 番目のテストケースにおいて、S を T に一致させることは不可能です。

4 番目のテストケースにおいて、S は s です。これに対して、次のように操作を行うことで S を T に一致させることが可能です。

  1. U_1 は B である。S の 1 文字目を削除することで、S は空文字列になる。
  2. U_2 は B である。S は空文字列なので、何もしない。
  3. U_3 は A である。S の先頭に t を挿入することで、S は t になる。

Problem Statement

You are given strings S, T, and U. The strings S and T consist of lowercase English letters (a–z), and U consists of A and B.

You will perform on S the following operation for i = 1, \dots, |U| in order. Determine if you can make S equal to T.

  • If U_i is A, insert any lowercase English character at any position in S.
  • If U_i is B and S is nonempty at that point, remove any one character from S.
  • If U_i is B and S is empty at that point, do nothing.

Given C test cases, solve each of them.

Constraints

  • C is an integer.
  • 1 \leq C \leq 5\,000
  • S and T are strings consisting of lowercase English letters (a–z).
  • 1 \leq |S| \leq 5\,000
  • 1 \leq |T| \leq 5\,000
  • U is a string consisting of A and B.
  • 1 \leq |U| \leq 5\,000
  • For each input file, the sum of \max(|S|, |T|, |U|) over all test cases is 5\,000.

Input

The input is given from Standard Input in the following format:

C
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_C

\mathrm{case}_i denotes the i-th test case. Each test case is given in the following format:

S
T
U

Output

Print C lines.

The i-th line should contain Yes if S can be made equal to T, and No otherwise, for the i-th test case.

Sample Input 1

4
cue
cube
A
club
cube
AB
crab
cube
AB
s
t
BBA

Sample Output 1

Yes
Yes
No
Yes

For the 1-st test case, S is cue. You can make S equal to T by performing operations as follows:

  1. U_1 is A. By inserting b right after the 2-nd character of S, it becomes cube.

For the 2-nd test case, S is club. You can make S equal to T by performing operations as follows:

  1. U_1 is A. By inserting e right after the 4-th character of S, it becomes clube.
  2. U_2 is B. By removing the 2-nd character of S, it becomes cube.

For the 3-rd test case, S cannot be made equal to T.

For the 4-th test case, S is s. You can make S equal to T by performing operations as follows:

  1. U_1 is B. By removing the 1-st character of S, it becomes an empty string.
  2. U_2 is B. Since S is empty, do nothing.
  3. U_3 is A. By inserting t right after the beginning of S, it becomes t.