[AGC007F] Shik and Copying String

## 题目描述 Shikk 的工作是复制。有一天，Shikk 从他的上司那里拿到了一个由小写英文字母组成的长度为 $N$ 的字符串 $S_{0}$（假设这天是第 $0$ 天）。这之后第 $i$ 天的工作是把 $S_{i-1}$ 复制到 $S_{i}$。下文中的 $S_{i}[j]$ 表示字符串 $S_{i}$ 的第 $j$ 个字母。 Shikk 还不怎么习惯这个工作。每天，当 Shikk 从第一个字母开始按顺序复制字符串时，他有可能会写下和刚刚写下的字母相同的字母，而不是本来应该写下的字母。也就是说，$S_{i}[j]$ 要么与 $S_{i-1}[j]$ 相同，要么与 $S_{i}[j-1]$ 相同。（特别地，字符串开头的字母不可能出错。也就是说，$S_{i}[1]$ 必然与 $S_{i-1}[1]$ 相同。） 输入两个字符串 $S_{0}$ 和 $T$，请求出使得 $S_{i}$ 有可能与 $T$ 相同的最小的整数 $i$。如果这样的 $i$ 不存在，请输出 $-1$。 ## 输入输出格式 #### 输入格式 输入的第一行仅一个整数，即字符串长度 $N$； 第二行仅一个由小写英文字母组成的字符串，即 $S_{0}$； 第三行仅一个由小写英文字母组成的字符串，即 $T$。 #### 输出格式 仅一行一个整数，即题目描述中所求的整数 $i$。如果这样的 $i$ 不存在，请输出 $-1$。 ## 样例解释 #### 样例 1 解释 一种可能的最佳方案：$S_{0}= \texttt{abcde}$，$S_{1} = \texttt{aaccc}$，$S_{2} = \texttt{aaacc}$。 ## 说明 - $1\le N\le 10 ^ 6$； - $S_{0}$ 和 $T$ 的长度都等于 $N$； - $S_{0}$ 和 $T$ 均只由小写英文字母组成。

[problemUrl]: https://atcoder.jp/contests/agc007/tasks/agc007_f シックの仕事はコピー取りです。ある日、シックは上司から英小文字からなる長さ $ N $ の文字列 $ S_0 $ を受け取りました（この日を $ 0 $ 日目とします）。これ以降、$ i $ 日目の仕事は、文字列 $ S_{i-1} $ を $ S_i $ にコピーすることです。以下、$ S_i $ の $ j $ 番目の文字を $ S_i[j] $ と表します。 シックはまだこの仕事に慣れていません。毎日、文字列を先頭の文字から順に書き写していくのですが、正しい文字の代わりに誤って直前に書いた文字と同じ文字を書いてしまうことがあります。すなわち、$ S_i[j] $ は $ S_{i-1}[j] $ または $ S_{i}[j-1] $ のどちらかと等しくなります。（ただし、文字列の先頭の文字を書き間違えることはありません。すなわち、$ S_i[1] $ は必ず $ S_{i-1}[1] $ と等しくなります。） 二つの文字列 $ S_0 $ と $ T $ が与えられます。$ S_i $ が $ T $ と等しくなる可能性があるような最小の整数 $ i $ を求めてください。もしそのような $ i $ が存在しなければ、代わりに `-1` と答えてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ S_0 $ $ T $

$ S_i $ が $ T $ と等しくなる可能性のあるような $ i $ が存在するならば、そのような $ i $ のうち最小のものを出力せよ。そのような $ i $ が存在しなければ、代わりに `-1` と出力せよ。

5
abcde
aaacc

2

5
abcde
abcde

0

4
acaa
aaca

2

5
abcde
bbbbb

-1

### 制約 - $ 1\ \leq\ N\ \leq\ 1,000,000 $ - $ S_0 $ と $ T $ の長さはともに $ N $ である。 - $ S_0 $ と $ T $ はともに英小文字のみからなる。 ### Sample Explanation 1 $ S_0 $ = `abcde`, $ S_1 $ = `aaccc`, $ S_2 $ = `aaacc` のように、$ S_2\ =\ T $ となる可能性が存在します。