Courses

算法

哈希

Module: 哈希

Problem

6 /8

哈克贝利·费恩和两根弦

Theory Click to read/hide

如果我们有字符串 A 的哈希值等于 h_A 字符串 B 的哈希值等于 h_B，那么我们可以快速计算出字符串 AB 的哈希值：
h_AB = h_A * p^|B| + h_B <- 对所有事物进行模数计算
|B|在哪里- 字符串 B 的长度。

Problem

Huckleberry Finn 有两个长度相同的字符串 s 和 t。
Huckleberry Finn 喜欢字符串有相同的前缀（开头），因此他可以交换字符串 s 中的两个字符，使字符串 s 和 t 的公共前缀更大。
然而，这个技巧相当乏味，所以 Huckleberry Finn 要么根本不做，要么只做一次。

帮助 Huckleberry Finn 确定他可以获得的字符串 s 和 t 的最长公共前缀长度。

输入：
第一行包含一个自然数n(1 <= n <= 200000) - 字符串s和t的长度
第二行包含一个字符串 s，由小写拉丁字母组成。
第三行包含一个由小写拉丁字母组成的字符串 t。

输出：
打印一个自然数——公共前缀s和t的最大长度，可以通过字符串s中的两个字符最多交换一次得到。

示例：
<正文>

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking