← 返回题目列表

AtCoder · agc007_f

F. Shik 和复制字符串

中文机器翻译题面 查看原题

分数: 1500 点

问题陈述

Shik的工作很无聊。白天 0,他的老板给了他一个字符串 S_0 长度 N 仅由小写英文字母组成。在 i-日复一日 0,Shik 的工作是复制字符串 S_{i-1} 到字符串 S_i。我们表示 j第一个字母 S_i as S_i[j].

Shik 在这项工作中缺乏经验。每天,当他从第一个字母到最后一个字母逐一抄写时,他都会犯错误。也就是说,他有时会不小心写下他之前写过的同一封信,而不是正确的信。更具体地说, S_i[j] 等于 S_{i-1}[j] or S_{i}[j-1]。 (请注意 S_i[1] 始终等于 S_{i-1}[1].)

给你字符串 S_0 和另一个字符串 T。 请确定最小的整数 i 这样 S_i 可能等于 T。如果没有这样的 i 已存在,请打印 -1.

约束

  • 1 \leq N \leq 1,000,000
  • 的长度 S_0 和 T 都是 N.
  • 两者 S_0 和 T 由小写英文字母组成。

输入

输入由标准输入按以下格式给出:

N
S_0
T

输出

打印最小整数 i 这样 S_i 可能等于 T。如果没有这样的 i 存在,打印 -1 代替。


示例输入 1

5
abcde
aaacc

示例输出 1

2

S_0 = abcde, S_1 = aaccc 和 S_2 = aaacc 是一个可能的序列,使得 S_2 = T.


示例输入 2

5
abcde
abcde

示例输出 2

0

示例输入 3

4
acaa
aaca

示例输出 3

2

示例输入 4

5
abcde
bbbbb

示例输出 4

-1