← 返回题目列表

AtCoder · ttpc2019_k

K. 流通

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

配点: 100 点

問題文

长度 N 的 0 和 1 组成的字符串 S, T 。

考虑以下操作。 一个整数

  • 1 \leq x \leq N 选择 x 并选择字符串 分为 S = S_1\ldots S_N 输出为 S_1\ldots S_x 和 S_{x+1}\ldots S_N 并通过循环右移将它们组合在一起。

但是,字符串 U = U_1\ldots U_M 的循环右移是多少? 意思是改成 U_1\ldots U_{M-1}U_M 输出为 U_MU_1\ldots U_{M-1} 。另外,x=N 是一个字符串 S 循环地将整个内容向右移动。 例如,字符串 如果你操作为 S=01001 作为 x=3 ,字符串首先会被 010 和 01 通过循环向右移位,我们得到 001 和 10 ,所以操作结果的字符串是 00110 。

这个操作是一个字符串 通过对 S 执行此操作任意多次,字符串 请判断是否可以与 T 匹配。 如果你不能 在一行上输出 MuriyarokonnNaN , 如果可能,请在一行中输出最少的操作次数。 满足

制約

  • N 满足 1 \leq N \leq 10^{5} 的整数
  • S 和 T 满足 0 和 1 组成的字符串
  • \lvert S \rvert = \lvert T \rvert = N
  • S 中 0 和 T 中 0 数字相等 通过对
  • S 中 1 和 T 中 1 数字相等 通过对

入力

输入将以以下形式从标准输入给出。

N
S
T

出力

文字列 S 执行任意次数的操作,您可以创建一个字符串。 如果能够匹配 T ,则设置最小操作次数,否则 将每个 MuriyarokonnNaN 打印在一行上。


入力例 1

6
010101
010110

出力例 1

3

通过按以下顺序执行操作,字符串 S 作为字符串 您可以匹配 T 。 执行

  • x=1 操作
  • x=5 操作
  • x=6 操作

此时字符串 S 是通过操作 它更改为 010101 \to 011010 \to 101100 \to 010110 。


入力例 2

18
111101101001101001
111101101001101001

出力例 2

0

这已经是一场没有任何动作的比赛。


入力例 3

18
011110100101000100
000110010011100110

出力例 3

8