E - Shift String Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

0, 1 からなる長さの等しい文字列 A,B が与えられます。

A に対して以下の操作を 0 回以上何度でも行うことができます。

  • A の先頭の文字を末尾に移動させる。

A=B とするために必要な最小の操作回数を求めてください。
但し、どのように操作しても A=B とできない場合、代わりに -1 と出力してください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 1 \le T \le 10000
  • A,B は 0, 1 からなる文字列
  • 2 \le |A|=|B| \le 10^6
  • ひとつの入力について、 |A| の総和は 10^6 を超えない

入力

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

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

各テストケースは以下の形式で与えられる。

A
B

出力

T 行出力せよ。

i 行目には i 番目のテストケースについて、答えを出力せよ。

入力例 1

5
1010001
1000110
000
111
01010
01010
0101
0011
100001101110000001010110110001
101100011000011011100000010101

出力例 1

2
-1
0
-1
22

この入力には 5 個のテストケースが含まれます。

  • 1 番目のテストケースについて、 A= 1010001 、 B= 1000110 です。
    • A に操作を 2 回行うと A が 1010001 \rightarrow 0100011 \rightarrow 1000110 となり、 A=B とできます。
  • 2 番目のテストケースについて、どのように操作を行っても 000 を 111 にすることはできません。
  • 3 番目のテストケースについて、はじめから A=B です。

Score : 450 points

Problem Statement

You are given strings A and B of equal length consisting of 0 and 1.

You can perform the following operation on A zero or more times.

  • Move the first character of A to the end.

Find the minimum number of operations required to make A=B.
If it is impossible to make A=B no matter how you operate, print -1 instead.

You are given T test cases; find the answer for each of them.

Constraints

  • 1 \le T \le 10000
  • A and B are strings consisting of 0 and 1.
  • 2 \le |A|=|B| \le 10^6
  • For a single input, the sum of |A| does not exceed 10^6.

Input

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

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each test case is given in the following format:

A
B

Output

Print T lines.

The i-th line should contain the answer for the i-th test case.

Sample Input 1

5
1010001
1000110
000
111
01010
01010
0101
0011
100001101110000001010110110001
101100011000011011100000010101

Sample Output 1

2
-1
0
-1
22

This input contains five test cases.

  • For the first test case, A= 1010001 and B= 1000110.
    • By performing the operation on A twice, A becomes 1010001 \rightarrow 0100011 \rightarrow 1000110, which makes A=B.
  • For the second test case, no matter how you perform the operation, you cannot change 000 to 111.
  • For the third test case, A=B from the beginning.