← 返回题目列表

AtCoder · abc430_e

H. 移位字符串

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

分数: 450 点

问题陈述

给你字符串 A 和 B 等长,由以下组成 0 和 1.

您可以对 A 零次或多次。

  • 移动第一个字符 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

此输入包含五个测试用例。

  • 对于第一个测试用例, A= 1010001 和 B= 1000110.
    • 通过执行以下操作 A 两次, A 变为 1010001 \rightarrow 0100011 \rightarrow 1000110,这使得 A=B.
  • 对于第二个测试用例,无论你如何执行操作,都无法更改 000 to 111.
  • 对于第三个测试用例, A=B 从头开始。