专题进阶 · 字符串算法推荐总顺序 · 第 94 / 148 课

由多项式前缀推导子串指纹,正确处理长度与碰撞。

先学会这些,再进入本课 字符串 前缀和 模运算
还有 3 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 字符串算法

字符串哈希String Hashing

把子串映射成数值指纹,比较很快但有碰撞风险,不能无条件当作严格相等。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

由多项式前缀推导子串指纹,正确处理长度与碰撞。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

同一个字符串要比较许多子串,逐字符比较很贵。能否先计算一组可快速提取的数字摘要?

02一步步得到方法

把字符当作进制中的数字

先把 a..z 映射为 1..26,选基数 B 与模数 M。前缀递推 H[i+1]=(H[i]·B+value(s[i])) mod M,类似把数字接到已有数值末尾。

长度 L 的子串 [l,r) 指纹为 H[r]−H[l]·B^L,再取模。减掉的项恰好是前 l 个字符在更长前缀中占据的高位部分,所以剩下子串不依赖原位置。

相等指纹只是候选相等

不同字符串可能映射到同一余数,这叫碰撞;M 个余数不可能唯一编码无限多字符串。双模或随机基数可降低风险,但仍不是数学上的绝对相等证明。

要求确定正确时,指纹命中后再逐字符验证,或选择 KMP、后缀结构等确定性方法。比较不同长度子串还应比较长度,避免让不同问题对象混用摘要。

哈希值是便宜的指纹而非唯一身份

把字符串映射成模数范围内的整数,便于快速比较候选。但字符串可能无限多、余数只有有限个,碰撞在数学上不可避免,所以哈希相等只能说明需要进一步确认。

前缀哈希让子串查询不再重新扫描整段;公式还要减去前缀对当前位置的幂次贡献。若做二分最长公共前缀,哈希只是加速每次相等判定,正确性仍需明确碰撞处理策略。

03把一个小例子完全算清楚

s='ababc',B=31,为手算取 M=101。

步骤计算与状态为什么这样做
前缀 a、abH[1]=1,H[2]=331×31+2=33
前缀 aba、ababH[3]=14,H[4]=32每步取模 101
子串 [2,4)(32−33×31²) mod 101=33与 [0,2) 的 ab 一致

窄屏可左右滑动表格,阅读完整计算与理由。

前缀减法消除了位置影响,却没有消除哈希碰撞。

04为什么这个方法成立

  1. 展开前缀多项式可分成前 l 项乘 B^(r−l) 与后面子串两部分。
  2. 两者相减恰好保留子串对应多项式。
  3. 取模保持加减乘关系,因此公式正确;指纹相同反推文本相同则不成立。

05把推导翻译成代码

Python · 可独立运行的教学实现

class StringHash:
    def __init__(self, text, base=31, mod=1000000007):
        assert all("a" <= c <= "z" for c in text)
        self.mod, self.h, self.p = mod, [0], [1]
        for c in text:
            self.h.append((self.h[-1]*base+ord(c)-ord("a")+1)%mod)
            self.p.append(self.p[-1]*base%mod)
    def slice_hash(self,left,right):
        assert 0 <= left <= right < len(self.h)
        return (self.h[right]-self.h[left]*self.p[right-left])%self.mod

逐个理解关键决定

self.p[right-left]
指数是子串长度,不是右端下标。
%self.mod
规范化相减后的余数;不同语言对负余数的规则要另外处理。

06时间、空间与实现范围

预处理 O(n) 时间与空间,单次指纹提取 O(1)(固定宽度算术模型)。

若命中后比较原文,单次确定性比较仍最坏 O(L);大量碰撞会拖慢基于指纹的筛选。

07改变条件,检查哪里会出错

哈希相同就直接宣称字符串相同

对于严格正确任务必须验证或选确定性结构。

把固定模数当作绝不碰撞

双哈希或随机参数可降低某些风险,但精确任务仍应设计验证或使用无碰撞保证的方法。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

空子串指纹是多少?

需要一点提示

H[l]−H[l]·B⁰。

查看解析与答案

0,长度为 0。

练习 2 · 边界与辨析

M=1 会发生什么?

需要一点提示

所有数模 1。

查看解析与答案

所有指纹都为 0,完全失去筛选能力,展示模数选择的重要性。

练习 3 · 变式与迁移

比较不同位置相同子串,为什么要乘 B 的幂?

需要一点提示

前缀高位权重发生了位移。

查看解析与答案

H[l] 在 H[r] 中向高位移动了 r−l 位,不乘就无法正确抵消。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Princeton · 字符串算法

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。