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 $ です。