AT_arc154_b [ARC154B] New Place

题目描述

给你两个长度为 $N$ 的字符串 $S$ 和 $T$,仅包含英文小写字母。 你可以重复进行下面的操作(可以不执行): - 将 $S$ 的第一个字符删去,并将这个字符插入到 $S$ 的任意位置。 问你至少执行多少次操作使得 $S$ 与 $T$ 相等。

输入格式

第一行是一个整数 $N$。第二行是字符串 $S$,第三行是字符串 $T$。

输出格式

如果 $S$ 不可能与 $T$ 相等,输出 `-1`。 否则,输出使 $S$ 和 $T$ 相等所需的最小操作数。 @[hellolin](/user/751017) 译

说明/提示

### 制約 - $ 1\ \le\ N\ \le\ 2\ \times\ 10^5 $ - $ S,T $ は英小文字からなる長さ $ N $ の文字列 ### Sample Explanation 1 以下のように操作を行うことで $ 2 $ 回で $ S $ を $ T $ に一致させることができます。 - $ S $ の先頭の文字を削除する。そして、同じ文字 `a` を $ S $ の末尾に挿入する。$ S $ は `baba` となる。 - $ S $ の先頭の文字を削除する。そして、同じ文字 `b` を $ S $ の $ 2 $ 文字目と $ 3 $ 文字目の間に挿入する。$ S $ は `abba` となる。 $ 1 $ 回以下の操作で $ S $ を $ T $ に一致させることはできないため、答えは $ 2 $ です。