字符串

字符串哈希与 Rabin-Karp

思路：把串变成一个数

KMP 让文本指针不回头。字符串哈希走的是另一条路： 把每个子串映射成一个整数，比较两个子串就退化成比较两个数。

把字符串看成一个 base 进制的数：

"abc" → 'a'×base² + 'b'×base¹ + 'c'×base⁰

数会很大，所以对一个质数 mod 取模：

两个常量的选法有讲究，下一节就是专门讲它的：

// BASE 取小质数（131 / 137 / 13331），MOD 取大质数。
// 🚨 判据是 BASE × MOD < 2^53 —— 理由见下一节，选大 BASE 会 100% 算错
const MOD = 1_000_000_007, BASE = 131;
function hashOf(s) {
  let h = 0;
  for (let i = 0; i < s.length; i++) h = (h * BASE + s.charCodeAt(i)) % MOD;
  return h;
}

⭐ 关键性质：加一个字符是 O(1)，去掉开头一个字符也是 O(1)。 所以窗口向右滑一格，哈希值可以直接推出来，不用重算 —— 这就是「滚动哈希」。

🚨 JavaScript 特有的坑：乘法悄悄越过 2^53

这是本篇最该记住的一节。别的语言讲字符串哈希会先讲冲突， JS 里更早撞上的是精度。

Number 只能精确表示到 2^53 - 1 = 9007199254740991。超过之后不报错、不抛异常， 只是悄悄给你一个近似值。

坑一：不取模，直接累乘

let h = 0;
for (const c of s) h = h * 131 + c.charCodeAt(0);   // ⚠️ 没有 % MOD

实测：base = 131 时，长度 8 的串就越过 2^53 了。八个字符。

长度 7   全 'a' 494000571725989   全 'z' 621320306706914    都还没越 2^53
长度 8   全 'a' 64714074896104656                           连最小值都越了

⚠️ 不过「越界」不等于「每个都算错」：长度 7 的 3000 个随机串一个都没错， 长度 8 的错 2741 个（91.4%） —— 剩下 8.6% 恰好落在仍能精确表示的偶数上。 📌 这让它更阴险：你随手试几个可能正好蒙对。

坑二：取模了，但 base × mod 越过 2^53

(h * base + c) % MOD 里，h 最大是 MOD - 1。所以真正的判据是：

📌 base × mod 必须 < 2^53。

base = 131          base × MOD = 1.31e+11   ✅ 安全
base = 999999937    base × MOD = 1.00e+18   ❌ 溢出

实测 3000 个随机串，拿 BigInt 当真值对照：

base = 131          与真值不符 0 个
base = 999999937    与真值不符 3000 个 —— 100%，全错

⚠️ 「随机选个大 base 更安全」是个害人的直觉：大 base 在 JS 里 100% 算错， 而且照样不报错。选 131 / 137 / 13331 这类小质数就够了。

坑三：前缀哈希查任意区间 —— 这一步必须拆分乘法

想 O(1) 查任意子串的哈希（不只是滑动窗口），标准做法是前缀哈希：

sub(i, len) = (pre[i + len] - pre[i] * pow[len]) % MOD

🚨 pre[i] 和 pow[len] 都是 mod 量级（接近 1e9）， 乘起来 1e9 × 1e9 = 1e18 —— 远远越过 2^53。

实测直接写 pre[i] * pow[len] % MOD，拿 BigInt 对照 20 万组随机 (a, b)：

直接写 a * b % m     错 155973 / 200000 = 78.0%

修法是把 a 拆成高低 16 位，让每一步中间量都待在 2^53 以内：

function mulmod(a, b, m) {
  const ah = Math.floor(a / 65536), al = a % 65536;
  return ((ah * b % m) * 65536 + al * b) % m;
}

为什么这样安全：ah < 1e9 / 65536 ≈ 15259，所以 ah * b < 15259 × 1e9 ≈ 1.53e13， 后面几步同样都在 1e14 以内 —— 全部 < 9e15。同样 20 万组：mulmod 错 0 个。

⭐ 判据很干净：两个乘数里只要有一个是「mod 量级」，就得用 mulmod。

  • 滚动哈希 h * BASE：BASE 是 131，小 → 直接乘就行
  • 前缀哈希 pre[i] * pow[len]：两个都是大数 → 必须 mulmod

同样叫「字符串哈希」，一个安全一个不安全，区别只在这里。

⚠️ 我自己在写这一篇时栽了三次

不是修辞。写这篇的验证脚本时，我在同一个坑上连摔三次：

栽在哪 症状
随机数生成器写了 seed * 1103515245 2.4e18 越界 → 20 万个「随机」串里只有 5646 个不同的，重复率 97.18%
滚动哈希写了 + MOD * MOD 去凑正数 1e18 越界 → Rabin-Karp 3000 组测试错 2190 组
前缀哈希写了 pre[i] * pow[len] 1e18 越界 → 最长重复子串 500 组错 438 组

🚨 第一条最阴险：它让我的测试数据失真，于是「碰撞 0 次」这个结论看起来 很正常，实际上根本没测到。观测手段自己坏了，比被观测的东西坏了更难发现 —— 因为一切看起来都是绿的。

📌 所以校准的办法是拿已知真值反推：26¹⁶ ≈ 4e22，20 万个 16 字随机串 重复率理应≈0；量出 97.18% 就说明生成器有问题，而不是「随机就是这样」。

冲突：实测紧贴生日悖论

哈希把无穷多的串映射到 mod 个值上，撞是必然的。问题是多快撞上。

生日悖论给出的估计：n 个串时期望碰撞数 ≈ n² / (2m)。 实测（mod = 1e9+7，16 字随机串，已去重保证 n 个都不同，11 个种子取中位数）：

不同串数 n 实测碰撞（区间） 生日悖论预测
10,000 0 (0~0) 0.05
50,000 1 (0~3) 1.25
100,000 5 (3~7) 5.00
200,000 19 (14~25) 20.00
400,000 77 (62~102) 80.00

⭐ 中位数紧贴理论预测 —— 这不是小概率意外，是可以算出来的常规事件。 十万个串就能撞上几个。 ⚠️ 但注意区间宽度：40 万那行从 62 到 102。碰撞数本身波动很大，报单个值没有意义。

主动构造一对碰撞也很便宜（10 字随机串）：

h("laorgekjhq") = h("jkhlrxwsfb") = 976983645     ← 这一对可以直接复现
试到第几个串才撞上：中位数 28824（11 个种子，区间 9353 ~ 57367）
理论期望 sqrt(π·m/2) = 39633     （sqrt(m) ≈ 31623 是同一量级的粗估）

⚠️ 「试了三万多个」这种数字换个种子能差六倍（9353 vs 57367）， 所以要记的是量级 √m，不是某个具体次数。

📌 这就是为什么竞赛里不要用固定的 base 和 mod：对手知道你的参数， 可以离线构造出让你 TLE 或 WA 的数据。力扣上没人卡你，随便用。

双模：把两个哈希拼起来

// 用两组不同的 (base, mod)，同时相等才算相等
const key = `${h1(s)}|${h2(s)}`;

同一批数据上（11 个种子，中位数）：

20 万个不同串    单模碰撞 19 次（14~25）    双模碰撞 0 次（11 个种子全 0）
40 万个不同串    单模碰撞 77 次（62~102）   双模碰撞 0 次（11 个种子全 0）

📌 单模那两个数与上面碰撞表是同一个量，所以取的是同一组中位数 （早先这两处写成 17 和 67，是另一批数据 —— 同一个量在一篇里出现两个值， 读者会以为是两回事）。

碰撞概率从 1/m 降到约 1/m²（1e18 分之一）。代价是常数翻倍。

⭐ 更省事的做法：哈希相等时再逐字符复核一次。命中很少，复核几乎不花时间， 而且是确定性正确的 —— 下面 Rabin-Karp 的实现用的就是这招。

Rabin-Karp：滚动哈希做字符串匹配

function rabinKarp(s, p) {
  const n = s.length, m = p.length;
  if (m === 0) return 0;
  if (m > n) return -1;

  let pow = 1;
  for (let i = 0; i < m - 1; i++) pow = pow * BASE % MOD;   // BASE^(m-1)

  let hp = 0, hs = 0;
  for (let i = 0; i < m; i++) {
    hp = (hp * BASE + p.charCodeAt(i)) % MOD;
    hs = (hs * BASE + s.charCodeAt(i)) % MOD;
  }

  for (let i = 0; ; i++) {
    // ⭐ 哈希相等只是「疑似」，逐字符复核之后才敢返回
    if (hs === hp && s.substr(i, m) === p) return i;
    if (i + m >= n) break;

    // 🚨 这里是 + MOD，不是 + MOD * MOD
    //    后者 1e18 越过 2^53 —— 我第一版就这么写的，3000 组错了 2190 组
    hs = ((hs - s.charCodeAt(i) * pow % MOD + MOD) % MOD * BASE
          + s.charCodeAt(i + m)) % MOD;
  }
  return -1;
}

滚出去一个字符要减 s[i] × BASE^(m-1)，减完可能是负数，所以 + MOD 再取模。

⚠️ 单模式串匹配：别用 Rabin-Karp

正确性没问题（5000 组随机用例上 RK / KMP / indexOf 结果完全一致， 三者都返回 1998000），但性能上它两头不讨好。 最坏用例（200 万个 a 加一个 b，模式串 2000 个 a 加 b，7 轮取中位数）：

Rabin-Karp    34.9 ms   (34.6~50.8)
KMP           10.5 ms   (10.0~12.2)      RK 慢 3.3×
indexOf        1.0 ms   (1.0~1.0)        RK 慢 36×

⚠️ 前两行的比值依赖 KMP 怎么写（换一版实现能在 2.6× 到 3.3× 之间移动）； indexOf 那一行才是稳的 —— 它是引擎原生实现，慢三十几倍这个量级不会变。

👉 就找一个子串在哪，直接用 indexOf。 引擎的实现是原生的， 你写什么都快不过它。要求手写就写 KMP。

⭐ 那 Rabin-Karp 到底赢在哪：它能做 KMP 做不了的事

哈希的真正价值不是「匹配得快」，是它把「子串相等」变成了 O(1) 的可比较值。 一旦子串能 O(1) 比较，很多题的解法就换了一个量级。

典型是最长重复子串（力扣 #1044）：找出在串里出现至少两次的最长子串。

思路：二分答案 + 前缀哈希。长度 L 可行（存在重复的长度-L 子串） 对 L 是单调的 —— 有长度 L 的重复串，就一定有长度 L-1 的。 所以二分 L，每次用哈希把所有长度 L 的子串扔进 Set 看有没有重复，O(n) 一趟。

🚨 但「扔进 Set 看有没有重复」这一步必须复核，否则答案是错的

上面那节刚算过：6 万个哈希在 1e9 的空间里期望碰撞 1.8 次。 而二分会试十几个不同的 L —— 只要在某个大 L 上误报一次重复，答案就被顶上去。

实测 6 万字符、4 种字母、11 个随机种子：

             纯哈希（撞了就当重复）        哈希 + 逐字符复核
答案          5435 / 21508 / 45007 …      14 / 14 / 15 …
答错次数      11 / 11  ← 一次都没对        0 / 11

⚠️ 纯哈希版 11 个种子全军覆没，答出来的是几千到几万 —— 而真值只有 14~18（理论上随机串的最长重复子串 ≈ 2·log₄(60000) = 15.9）。 🚨 这不是小概率事件：碰撞期望 1.8 次，而二分把每个 L 都问一遍， 误报一次就够了。

📌 复核的代价很小（碰撞极少，几乎不触发逐字符比较）：

纯哈希（错的）             70 ms
哈希 + 逐字符复核         137 ms      ← 慢一倍，但答案对
二分 + 真子串 Set（确定）  16446 ms    ← 不用哈希，直接比字符串
真正的 O(n²) 逐对比较      约 9000 ms（由 n=12000 的 359 ms 按平方外推）

⭐ 所以真正的对比是 137 ms vs 约 9000 ms ≈ 65× —— 优势依然是数量级的。 👉 而这一节的教训是：上面讲的「碰撞是常规事件」不是背景知识，是这道题的实现要求。 「哈希相等时再逐字符复核」那句话不是可选项。

⚠️ 这道题 KMP 帮不上忙 —— KMP 回答的是「p 在 s 里吗」， 而这里没有给定的 p，要找的恰恰是那个 p。

📌 同一类的还有：#187 重复的 DNA 序列、#1316 不同的循环子字符串、 #1147 段式回文。共同点都是**「要拿很多子串互相比」**， 而不是「拿一个模式串去比」。

小结：三条判据

问题 用什么
找一个子串在哪 indexOf；不许用内置就 KMP
大量子串互相比较 / 二分答案 字符串哈希
需要 next 数组的性质（最短回文、重复子串周期） KMP

以及那条 JS 专属的：

🚨 写下任何 a * b 之前，先问一句「这两个数最大能到多少」。 乘积过了 9007199254740991，JavaScript 不会告诉你。

练习

勾选记录做过哪些，0 / 6 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。