#P12915. [AGC007F] Shik and Copying String

    ID: 12099 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-逆向思考支配关系同向双指针

[AGC007F] Shik and Copying String

题目描述

Shikk 的工作是复制。有一天,Shikk 从他的上司那里拿到了一个由小写英文字母组成的长度为 NN 的字符串 S0S_{0}(假设这天是第 00 天)。这之后第 ii 天的工作是把 Si−1S_{i-1} 复制到 SiS_{i}。下文中的 Si[j]S_{i}[j] 表示字符串 SiS_{i} 的第 jj 个字母。

Shikk 还不怎么习惯这个工作。每天,当 Shikk 从第一个字母开始按顺序复制字符串时,他有可能会写下和刚刚写下的字母相同的字母,而不是本来应该写下的字母。也就是说,Si[j]S_{i}[j] 要么与 Si−1[j]S_{i-1}[j] 相同,要么与 Si[j−1]S_{i}[j-1] 相同。(特别地,字符串开头的字母不可能出错。也就是说,Si[1]S_{i}[1] 必然与 Si−1[1]S_{i-1}[1] 相同。)

输入两个字符串 S0S_{0} 和 TT,请求出使得 SiS_{i} 有可能与 TT 相同的最小的整数 ii。如果这样的 ii 不存在,请输出 −1-1。

样例解释

样例 1 解释

一种可能的最佳方案:S0=abcdeS_{0}= \texttt{abcde},S1=aacccS_{1} = \texttt{aaccc},S2=aaaccS_{2} = \texttt{aaacc}。

输入格式

输入的第一行仅一个整数,即字符串长度 NN;

第二行仅一个由小写英文字母组成的字符串,即 S0S_{0};

第三行仅一个由小写英文字母组成的字符串,即 TT。

输出格式

无

输入输出样例 #1

输入 #1

5
abcde
aaacc

输出 #1

2

输入输出样例 #2

输入 #2

5
abcde
abcde

输出 #2

0

输入输出样例 #3

输入 #3

4
acaa
aaca

输出 #3

2

输入输出样例 #4

输入 #4

5
abcde
bbbbb

输出 #4

-1

说明/提示

  • 1≤N≤1061\le N\le 10 ^ 6;
  • S0S_{0} 和 TT 的长度都等于 NN;
  • S0S_{0} 和 TT 均只由小写英文字母组成。