← 返回题目列表

Codeforces · 533/E

E. 纠正错误

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

分析人们在输入搜索查询时所犯的错误是一项复杂而有趣的工作。由于没有保证的方法可以确定用户输入某些查询的最初含义,因此我们必须使用不同类型的启发式方法。

Polycarp 需要编写一个代码,可以在给定两个单词的情况下检查它们是否可以由于拼写错误而从同一个单词中获得。波利卡普斯指出,最常见的拼写错误是在键入单词时恰好跳过一个字母。

实现一个程序,给定两个相同长度 n 的不同单词 S 和 T,确定有多少个长度为 n + 1 的单词 W,并且具有这样的属性,您可以通过删除一个字符将 W 转换为 S 和 T。单词 S 和 T 由小写英文字母组成。单词 W 也应由小写英文字母组成。

输入

第一行包含整数 n (1 ≤ n ≤ 100 000) — 单词 S 和 T 的长度。

第二行包含单词 S。

第三行包含单词 T。

单词S和T由小写英文字母组成。保证S和T是不同的词。

输出

打印一个整数——由于拼写错误而可以转换为 S 和 T 的不同单词 W 的数量。

示例

输入 #1

7
reading
trading

输出 #1

1

输入 #2

5
sweet
sheep

输出 #2

0

输入 #3

3
toy
try

输出 #3

2

注意

在第一个样本测试中,两个给定单词只能从单词“treading”中获得(删除的字母以粗体标记)。

在第二个示例测试中,无法通过删除一个字母从同一个单词中获得两个给定单词。

在第三个示例测试中,两个给定单词可以从单词“tory”或单词“troy”获得。