← 返回题目列表

AtCoder · arc181_b

B. 烦人的字符串问题

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

对于字符串 S 和 T 由小写英文字母和字符串组成 X 组成 0 和 1,定义字符串 f(S,T,X) 由小写英文字母组成,如下:

  • 以空字符串开头,对于每个 i=1,2,\dots,|X|,追加 S 到最后如果 i- 第一个字符 X is 0,并附加 T 到最后,如果是 1.

给你一个字符串 S 由小写英文字母和字符串组成 X 和 Y 组成 0 和 1.

判断是否存在字符串 T (可以为空)使得 f(S,T,X)=f(S,T,Y).

你有 t 测试用例解决。

约束

  • 1 \leq t \leq 5 \times 10^5
  • 1 \leq |S| \leq 5\times 10^5
  • 1 \leq |X|,|Y| \leq 5\times 10^5
  • S 是由小写英文字母组成的字符串。
  • X 和 Y 是由以下组成的字符串 0 和 1.
  • 总和 |S| 在单个输入中的所有测试用例最多 5 \times 10^5.
  • 总和 |X| 在单个输入中的所有测试用例最多 5 \times 10^5.
  • 总和 |Y| 在单个输入中的所有测试用例最多 5 \times 10^5.

输入

输入由标准输入按以下格式给出:

t
\mathrm{case}_1
\vdots
\mathrm{case}_t

每个案例均按以下格式给出:

S
X
Y

输出

打印 t 行。的 i- 第行应包含 Yes 如果存在 T 满足条件 i- 第一个测试用例,以及 No 否则。


示例输入 1

3
araara
01
111
araaaa
100100
0010111
abacabac
0
1111

示例输出 1

Yes
No
No

下面,字符串连接用 +.

对于第一个测试用例,如果 T=ara,那么 f(S,T,X)=S+T=araaraara 和 f(S,T,Y)=T+T+T=araaraara,所以 f(S,T,X)=f(S,T,Y).

对于第二个和第三个测试用例,没有 T 满足条件。


示例输入 2

2
empty
10101
00
empty
11111
111

示例输出 2

Yes
Yes

T 可以为空。