D - ビーズ列 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

高橋君は、A と B の 2 種類の文字からなる長さ N の文字列で表されるビーズ列を持っています。ビーズ列は先頭と末尾が区別される線形の列です。ビーズ列の初期状態は文字列 S で表されます。

高橋君は、ビーズ列に対して次の 3 種類の操作を、好きな順序で 0 回以上、合計何回でも行うことができます。各操作はその時点でのビーズ列の状態に対して適用されます。

  • 左に回転：ビーズ列を巡回左シフトする。すなわち、先頭の 1 文字を取り除き、末尾に付加する。
  • 右に回転：ビーズ列を巡回右シフトする。すなわち、末尾の 1 文字を取り除き、先頭に付加する。
  • パターン複製：N の正の約数 d（d < N）を 1 つ選ぶ。d の値は操作ごとに自由に選ぶことができる。現在のビーズ列の先頭 d 文字をパターン P とし、ビーズ列全体を P を N / d 回繰り返して連結した文字列で置き換える。

高橋君は、ビーズ列を目標の文字列 T と一致させたいです。

S を T に一致させるために必要な最小の操作回数を求めてください。S がすでに T と一致している場合は 0 を出力してください。どのように操作しても T に一致させられない場合は -1 を出力してください。

制約

  • 1 \leq N \leq 25
  • S は A と B からなる長さ N の文字列
  • T は A と B からなる長さ N の文字列

入力

N
S
T

N はビーズ列の長さを表す整数、S は初期状態のビーズ列を表す文字列、T は目標のビーズ列を表す文字列である。

出力

S を T に一致させるために必要な最小の操作回数を 1 行で出力せよ。一致させられない場合は -1 を出力せよ。

入力例 1

6
ABBAAA
ABABAB

出力例 1

1

入力例 2

5
AAAAB
AABAB

出力例 2

-1

入力例 3

12
BAABABBAAAAA
ABBAABBAABBA

出力例 3

3

入力例 4

24
BABAAABBABBBABAAAABBABBA
AABBABAABBABAABBABAABBAB

出力例 4

5

入力例 5

1
A
A

出力例 5

0

Score : 400 pts

Problem Statement

Takahashi has a bead sequence represented by a string of length N consisting of two types of characters: A and B. The bead sequence is a linear sequence where the front and back are distinguished. The initial state of the bead sequence is represented by the string S.

Takahashi can perform the following 3 types of operations on the bead sequence, in any order, zero or more times, for any total number of times. Each operation is applied to the current state of the bead sequence.

  • Rotate left: Perform a cyclic left shift on the bead sequence. That is, remove the first character and append it to the end.
  • Rotate right: Perform a cyclic right shift on the bead sequence. That is, remove the last character and prepend it to the front.
  • Pattern duplication: Choose a positive divisor d of N (d < N). The value of d can be freely chosen for each operation. Let P be the first d characters of the current bead sequence, and replace the entire bead sequence with the string obtained by repeating P exactly N / d times concatenated together.

Takahashi wants to make the bead sequence match the target string T.

Find the minimum number of operations required to make S match T. If S already matches T, output 0. If it is impossible to make S match T no matter what operations are performed, output -1.

Constraints

  • 1 \leq N \leq 25
  • S is a string of length N consisting of A and B
  • T is a string of length N consisting of A and B

Input

N
S
T

N is an integer representing the length of the bead sequence, S is a string representing the initial state of the bead sequence, and T is a string representing the target bead sequence.

Output

Output in one line the minimum number of operations required to make S match T. If it is impossible to make them match, output -1.

Sample Input 1

6
ABBAAA
ABABAB

Sample Output 1

1

Sample Input 2

5
AAAAB
AABAB

Sample Output 2

-1

Sample Input 3

12
BAABABBAAAAA
ABBAABBAABBA

Sample Output 3

3

Sample Input 4

24
BABAAABBABBBABAAAABBABBA
AABBABAABBABAABBABAABBAB

Sample Output 4

5

Sample Input 5

1
A
A

Sample Output 5

0