B - New Place Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

長さ N の英小文字からなる文字列 S,T が与えられます。

あなたは以下の操作を好きな回数（0 回でもよい）繰り返すことができます。

  • S の先頭の文字を削除し、同じ文字を S の任意の位置に挿入する。

S を T に一致させることができるか判定し、できるのであれば必要な最小の操作回数を求めてください。

制約

  • 1 \le N \le 2 \times 10^5
  • S,T は英小文字からなる長さ N の文字列

入力

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

N
S
T

出力

S を T に一致させることが出来ない場合 -1 を出力せよ。一致させることができる場合必要な最小の操作回数を出力せよ。

入力例 1

4
abab
abba

出力例 1

2

以下のように操作を行うことで 2 回で S を T に一致させることができます。

  • S の先頭の文字を削除する。そして、同じ文字 a を S の末尾に挿入する。S は baba となる。
  • S の先頭の文字を削除する。そして、同じ文字 b を S の 2 文字目と 3 文字目の間に挿入する。S は abba となる。

1 回以下の操作で S を T に一致させることはできないため、答えは 2 です。

入力例 2

3
arc
cra

出力例 2

2

Score : 400 points

Problem Statement

You are given strings S and T of length N consisting of lowercase English letters.

You can repeat the following operation any number of times (possibly zero).

  • Erase the first character of S and insert the same character at any position of S.

Determine whether it is possible to make S equal T, and if it is possible, find the minimum number of operations needed.

Constraints

  • 1 \le N \le 2 \times 10^5
  • S and T are strings of length N consisting of lowercase English letters.

Input

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

N
S
T

Output

If it is impossible to make S equal T, print -1. If it is possible, print the minimum number of operations needed.

Sample Input 1

4
abab
abba

Sample Output 1

2

You can make S equal T in two operations, as follows.

  • Erase the first character of S, and insert that character a at the end of S, making S baba.
  • Erase the first character of S, and insert that character b between the 2-nd and 3-rd characters of S, making S abba.

It is impossible to make S equal T in one or fewer operations, so the answer is 2.

Sample Input 2

3
arc
cra

Sample Output 2

2