/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 600 点
問題文
英小文字からなる文字列 S,T および 0, 1 からなる文字列 X に対し、英小文字からなる文字列 f(S,T,X) を以下のように定めます。
- 空文字列に対し、 i=1,2,\dots,|X| の順に、 X の i 文字目が
0なら S を、1なら T を末尾に結合することで得られる文字列
英小文字からなる文字列 S および 0, 1 からなる文字列 X,Y が与えられます。
英小文字からなる文字列 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からなる文字列 - 1 つの入力に含まれるテストケースについて、 |S| の総和は 5 \times 10^5 以下
- 1 つの入力に含まれるテストケースについて、 |X| の総和は 5 \times 10^5 以下
- 1 つの入力に含まれるテストケースについて、 |Y| の総和は 5 \times 10^5 以下
入力
入力は以下の形式で標準入力から与えられる。
t
\mathrm{case}_1
\vdots
\mathrm{case}_t
各ケースは以下の形式で与えられる。
S X Y
出力
t 行出力せよ。 i 行目には i 番目のテストケースについて、条件を満たす T が存在するならば Yes を、存在しないならば No を出力せよ。
入力例 1
3 araara 01 111 araaaa 100100 0010111 abacabac 0 1111
出力例 1
Yes No No
以下、文字列の結合を + を用いて表します。
1 番目のテストケースについて、 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) が成り立ちます。
2,3 番目のテストケースについて、条件を満たす T は存在しません。
入力例 2
2 empty 10101 00 empty 11111 111
出力例 2
Yes Yes
T は空文字列であっても構いません。
Score : 600 points
Problem Statement
For strings S and T consisting of lowercase English letters, and a string X consisting of 0 and 1, define the string f(S,T,X) consisting of lowercase English letters as follows:
- Starting with an empty string, for each i=1,2,\dots,|X|, append S to the end if the i-th character of X is
0, and append T to the end if it is1.
You are given a string S consisting of lowercase English letters, and strings X and Y consisting of 0 and 1.
Determine if there exists a string T (which can be empty) such that f(S,T,X)=f(S,T,Y).
You have t test cases to solve.
Constraints
- 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 is a string consisting of lowercase English letters.
- X and Y are strings consisting of
0and1. - The sum of |S| across all test cases in a single input is at most 5 \times 10^5.
- The sum of |X| across all test cases in a single input is at most 5 \times 10^5.
- The sum of |Y| across all test cases in a single input is at most 5 \times 10^5.
Input
The input is given from Standard Input in the following format:
t
\mathrm{case}_1
\vdots
\mathrm{case}_t
Each case is given in the following format:
S X Y
Output
Print t lines. The i-th line should contain Yes if there exists a T that satisfies the condition for the i-th test case, and No otherwise.
Sample Input 1
3 araara 01 111 araaaa 100100 0010111 abacabac 0 1111
Sample Output 1
Yes No No
Below, string concatenation is represented using +.
For the 1st test case, if T=ara, then f(S,T,X)=S+T=araaraara and f(S,T,Y)=T+T+T=araaraara, so f(S,T,X)=f(S,T,Y).
For the 2nd and 3rd test cases, there is no T that satisfies the condition.
Sample Input 2
2 empty 10101 00 empty 11111 111
Sample Output 2
Yes Yes
T can be empty.