分数: 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 可以为空。