多项式字符串哈希
在常数时间内比较子串
多项式字符串哈希 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
快速比较子字符串
您经常需要判断两个子字符串是否相等。逐个字符比较速度很慢，因此我们将每个字符串转换为一个数字。🔢
哈希的概念
哈希会将一个字符串映射为一个整数。如果两个字符串不同，它们的哈希值也几乎总是不同。
将字符串视为多项式
我们将每个字符视为 p 进制中的一位数字。这种多项式视角会把字符串转换成一个加权总和。
h = ord(s[0]) + ord(s[1]) * p + ord(s[2]) * p * p选择基数和模数
请选择一个像 31 这样的素数基数，以及一个较大的素数模数。取模可以让数字保持较小，并避免溢出。
BASE = 31
MOD = 10**9 + 9计算一个哈希值
遍历字符串，使用霍纳法则逐个合入字符，并在每一步都进行取模。
h = 0
for c in s:
h = (h * BASE + ord(c)) % MOD前缀哈希
为每个位置存储一个前缀哈希。这样，任意子字符串的哈希值都可以通过快速减法得到。
pre[i + 1] = (pre[i] * BASE + ord(s[i])) % MOD基数的幂
您还需要预先计算基数的幂。相减时，它们可以将两个前缀对齐。
pw[i] = (pw[i - 1] * BASE) % MODO(1) 时间求子字符串哈希
s[l..r] 的哈希值可以通过两个前缀哈希的减法得到，并乘以相应的幂进行缩放。每次查询只需常数时间。
def sub(l, r):
return (pre[r] - pre[l] * pw[r - l]) % MOD注意碰撞
两个不同的字符串可能拥有相同的哈希值，这就是碰撞。这种情况很少见，但竞赛有时会精心构造输入来触发它。
用双重哈希提高安全性
使用两个相互独立的模数，并比较两个哈希值。两个哈希值同时发生碰撞的情况实际上不可能发生。
哈希的用武之地
哈希可以用于子串比较、查找重复内容和模式搜索。它是一种灵活的多功能工具。
快速检查
选择合适的工具，以安全地比较大量子串。
回顾：哈希的优势
现在您可以将字符串转换为多项式哈希值，在 O(1) 时间内查询任意子串，并防范碰撞。🚀
常见问题解答
「多项式字符串哈希」课时是免费的吗？
是的 — 「多项式字符串哈希」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「多项式字符串哈希」这节课中我会学到什么？
在常数时间内比较子串 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。
「多项式字符串哈希」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- KMP 前缀函数
- 多项式字符串哈希
- 用于模式搜索的 Z 函数
- 使用字典树进行前缀查找