分数: 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