题目描述

有两个长度相同、仅由 $0$ 和 $1$ 组成的字符串 $A = A_1A_2...A_n$ 和 $B = B_1B_2...B_n$。

你可以对 $A$ 进行如下操作，次数不限且顺序任意：

• 将 $A$ 向左循环移位一位（即将 $A=A_1A_2...A_n$ 变为 $A_2A_3...A_nA_1$）。
• 将 $A$ 向右循环移位一位（即将 $A=A_1A_2...A_n$ 变为 $A_nA_1A_2...A_{n-1}$）。
• 任意选择一个 $B_i=1$ 的位置 $i$，将 $A_i$ 反转（即令 $A_i=1-A_i$）。

你的目标是使字符串 $A$ 和 $B$ 完全相同。

请输出使 $A$ 和 $B$ 相同所需的最小操作次数。如果无法做到，请输出 $-1$。

输入格式

输入以以下格式从标准输入读入：

$A$ $B$

输出格式

输出使字符串 $A$ 和 $B$ 完全相同所需的最小操作次数。如果无法实现，请输出 $-1$。

样例 1

输入

1010
1100

输出

3

样例 2

输入

1
0

输出

-1

样例 3

输入

11010
10001

输出

4

样例 4

输入

0100100
1111111

输出

5

说明/提示

限制条件

• $1 \leq |A|=|B| \leq 2{,}000$
• $A,B$ 仅包含 $0$ 和 $1$。

样例解释 1

以下是一种实现目标的最短操作序列：

• 反转 $A_1$：$A = 0010$
• 左移一次：$A = 0100$
• 再次反转 $A_1$：$A = 1100$

样例解释 2

没有办法反转 $A$ 的唯一一个比特。

样例解释 3

以下是一种实现目标的最短操作序列：

• 右移一次：$A = 01101$
• 反转 $A_5$：$A = 01100$
• 左移一次：$A = 11000$
• 再次左移一次：$A = 10001$

样例解释 4

只需按任意顺序依次反转 $A_1$、$A_3$、$A_4$、$A_6$、$A_7$ 即可。

由 ChatGPT 5 翻译