5.3 Substring Search：暴力、KMP、Boyer-Moore与Rabin-Karp

5.3 · Substring Search覆盖 5 个作者站正式主题，以章专属状态模型、逐步轨迹、反例恢复和独立预言机验收。

学习目标

  • 能解释“5.3 · Substring Search”如何比较暴力、KMP、Boyer-Moore 与 Rabin-Karp 如何复用失败信息减少文本回退
  • 能逐项核对 子字符串查找、暴力子字符串查找、KMP算法、Boyer-Moore算法、Rabin-Karp算法，并区分作者站内容与本页独立补充
  • 能按“KMP 在 DFA/前缀函数预处理后搜索 Θ(N)；Rabin-Karp 以滚动散列常数时间更新窗口”手算一个最小输入，逐步检查“任一时刻 j 表示模式前 j 个字符已与当前文本后缀匹配；报告位置必须通过字符验证”
  • 能注入“KMP 失配后错误地把文本指针和模式指针都回退，或 Rabin-Karp 命中哈希后不验字符”，保存基线、首个分叉、恢复和同输入重放证据

来源、版次与独立重写边界

“5·3 · Substring Search”对应 Robert Sedgewick 与 Kevin Wayne 的 Algorithms, Fourth Edition（Addison-Wesley Professional，2011）。对这一节，作者维护的本节页面提供与教材协同的浓缩正文、Java 实现、图示、习题和部分答案；全书作者站给出 6 章、30 节的完整结构，并明确区分在线资料与纸质教材的学习用途。

“5·3 · Substring Search”的作者页公开经授权的在线节选和配套资源，但不是整本教材全文。因此“5·3 · Substring Search”采用 independent-rewrite / authorized-sample：中文讲解、推导与实验独立组织，不声称逐段翻译；算法名称、API 和示例边界以作者页、官方代码索引及官方勘误交叉核对。

作者站章节坐标：5.3 · Substring Search

  • 1. 子字符串查找：在本页通过“预处理模式”连接解释、交互状态和练习验收。
  • 2. 暴力子字符串查找：在本页通过“扫描文本字符”连接解释、交互状态和练习验收。
  • 3. KMP算法：在本页通过“命中或计算失配跳转”连接解释、交互状态和练习验收。
  • 4. Boyer-Moore算法：在本页通过“验证候选窗口”连接解释、交互状态和练习验收。
  • 5. Rabin-Karp算法：在本页通过“返回位置或 N”连接解释、交互状态和练习验收。

从“失配以后，哪些已经比较过的字符还能复用”开始

给定length N的text和length M的pattern，子字符串查找（substring search）返回最小offset i，使：

∀ 0≤j<M,text[i+j]=pattern[j]\forall\,0\le j<M,\qquad text[i+j]=pattern[j]

先预测：某个alignment已经匹配pattern前5个字符，第6个失配，下一步是否一定只把pattern右移1并从j=0重比？暴力算法如此；KMP会利用已匹配prefix的border直接切到可行restart state；Boyer-Moore从右向左观察bad character并可能跳过多个alignments；Rabin-Karp则根本不逐字符比较大多数windows，只滚动更新fingerprint。

四种算法的区别不是“是否看字符”，而是失配或窗口移动时保存了什么information。统一验收仍然简单：candidate offset必须in bounds，length-M window逐字符等于pattern，并满足API要求的leftmost语义。

5.3.1 Search contract与边界

精确substring search应先定义：

  • 找到时返回leftmost occurrence还是任意occurrence。
  • 未找到返回N、-1或optional；官方实现返回N。
  • Empty pattern是否在offset 0匹配。
  • Pattern longer than text时直接not found。
  • Character unit是byte、UTF-16 code unit、code point还是normalized grapheme/collation unit。

本节跟随官方Java代码，以string charAt units和leftmost match为contract。生产系统若处理Unicode canonical equivalence，应先normalize pattern/text；否则visual-equal strings可能code units不同。

Search preprocessing是否可复用也影响API设计。若同一pattern查询大量texts，KMP DFA、Boyer-Moore right table或Rabin-Karp pattern hash可构造一次；若pattern每次变化，preprocessing必须计入total cost。

5.3.2 Brute-force substring search：每个alignment重新开始

暴力子字符串查找（brute-force substring search）枚举i从0到N-M：

public static int search(String pattern, String text) {
    int M = pattern.length();
    int N = text.length();
    for (int i = 0; i <= N - M; i++) {
        int j;
        for (j = 0; j < M; j++)
            if (text.charAt(i + j) != pattern.charAt(j)) break;
        if (j == M) return i;
    }
    return N;
}

Correctness直接：每个smaller offset都被完整排除，first full match就是leftmost。Extra space constant，no preprocessing。Worst case每个alignment匹配M-1 characters后才失配：

Tbrute=O((N−M+1)M)=O(NM)T_{\mathrm{brute}}=O((N-M+1)M)=O(NM)

Repeated characters制造典型bad case，例如pattern AAAAAAAB 与一长串A后接B。Random large-alphabet text通常在前几个characters失配，expected comparisons接近linear；所以brute force对short patterns、小inputs或one-off queries仍可能是最简单可靠的选择。

另一种single-loop写法在match时同时增加i/j，失配后执行 i -= j; j = 0。它与alignment版本等价，但index rollback更容易off-by-one；certificate应直接检查returned window，不信任pointer arithmetic。

5.3.3 KMP的核心：已匹配prefix的border也是suffix

Knuth-Morris-Pratt（Knuth-Morris-Pratt）把state j定义为“刚读取的text suffix与pattern length-j prefix相等”。读入next character c后，transition告诉我们新的longest valid prefix length。

若在j处失配，不必把j清零。此前matched substring可能有proper suffix同时是pattern prefix，这个border可作为restart。Pattern ABABAC在某些失配后仍保留 AB 或 ABAB 状态。

DFA construction：match edge与restart shadow

Official KMP构造R×M DFA。Column j的match character transition设为j+1；其余mismatch cases复制restart state x对应column。随后用current pattern character从x出发更新下一column的restart：

dfa[pat.charAt(0)][0] = 1;
for (int x = 0, j = 1; j < M; j++) {
    for (int c = 0; c < R; c++)
        dfa[c][j] = dfa[c][x];      // mismatch cases
    dfa[pat.charAt(j)][j] = j + 1;  // match case
    x = dfa[pat.charAt(j)][x];      // next restart state
}

复制restart transitions保留了所有可能的prefix/suffix overlap，而不是只记一个“失败就回几步”的magic number。DFA state M是accepting state，无需再建outgoing column。

Search：text index严格单调前进

int i, j;
for (i = 0, j = 0; i < N && j < M; i++)
    j = dfa[text.charAt(i)][j];
 
if (j == M) return i - M;
return N;

每个text character只做一次transition，i从不回退。Official dense-DFA implementation：

TKMP=Θ(RM+N),SKMP=Θ(RM)T_{\mathrm{KMP}}=\Theta(RM+N), \qquad S_{\mathrm{KMP}}=\Theta(RM)

KMPplus或prefix-function/failure-function版本可把preprocessing和space降到Theta(M)，独立于R。Dense DFA在small fixed alphabet和多次reuse pattern时简单直接；large Unicode alphabet不应盲目分配R×M table。

5.3.4 KMP correctness：state是可检验的suffix certificate

读完text prefix text[0..i] 后，state j必须等于pattern prefixes中、同时也是已读text suffix的maximum length：

j=max⁡{k:pattern[0..k)=text[i−k+1..i+1)}j=\max\{k: pattern[0..k)=text[i-k+1..i+1)\}

这个state invariant证明两件事：

  1. 若j=M，最后M个text characters就是pattern，start为i-M+1。
  2. 若j小于M，所有更长prefix candidates已由DFA transition排除，不会漏掉leftmost match。

Testing可在每一步用naive suffix oracle重算j，与DFA state对照。这样能定位某一DFA column的restart construction错误，而不是只在final offset上看fail。

若要找all matches，accept后不能简单stop；应输出start，再把state转到pattern的proper border restart并继续消费text，才能发现overlapping matches，例如pattern AAA in AAAAA。

5.3.5 Boyer-Moore：从右向左，用bad character跳过alignments

Boyer-Moore算法（Boyer-Moore）预处理 right[c]：character c在pattern中的rightmost index，不出现则为-1。

At alignment i，从j=M-1向0比较。若pattern[j]与text[i+j]失配，bad character为c，安全skip：

skip=max⁡(1, j−right[c])skip=\max(1,\ j-right[c])

如果c不在pattern中，right[c]=-1，可把pattern移过该bad character；若c在pattern更左位置，就让那个occurrence与text c对齐；若right[c]在j右侧，formula可能非正，所以至少move 1。

for (int i = 0; i <= N - M; i += skip) {
    skip = 0;
    for (int j = M - 1; j >= 0; j--) {
        if (pat.charAt(j) != text.charAt(i + j)) {
            skip = Math.max(1, j - right[text.charAt(i + j)]);
            break;
        }
    }
    if (skip == 0) return i;
}

Official Section 5.3 implementation只有bad-character rule，不包含strong good-suffix rule。Typical text可一次跳过多个characters并少于N次比较；但bad-character-only worst case仍可到O(NM)。不能把完整Boyer-Moore的更强heuristics或average observations误写成该代码的guarantee。

它天然需要查看当前M-length window右端，适合random-access text；strict one-character-at-a-time stream上，KMP更自然。Large R时right table也可用map，只存pattern出现的characters。

5.3.6 Rabin-Karp：把M次比较变成rolling fingerprint

Rabin-Karp算法（Rabin-Karp）把M-character string当base-R integer并mod prime Q：

h(s)=(∑j=0M−1sjRM−1−j) mod Qh(s)=\left(\sum_{j=0}^{M-1}s_jR^{M-1-j}\right)\bmod Q

Pattern hash预计算一次。Text first window也花Theta(M)；之后令 RM=RM−1 mod QRM=R^{M-1}\bmod Q，从window i滚到i+1：

ti+1=((ti−txti⋅RM)R+txti+M) mod Qt_{i+1} =\bigl((t_i-txt_i\cdot RM)R+txt_{i+M}\bigr)\bmod Q

Implementation要先加Q再mod，避免语言的negative remainder使hash落在错误范围：

txtHash = (txtHash + Q - RM * txt.charAt(i - M) % Q) % Q;
txtHash = (txtHash * R + txt.charAt(i)) % Q;
if (patHash == txtHash && check(txt, i - M + 1))
    return i - M + 1;

每次window move只做constant modular arithmetic，因此expected search Theta(N)，preprocess Theta(M)，extra state constant（不计pattern）。它特别适合multiple equal-length patterns：把all pattern hashes放入set，rolling text hit后再查candidate bucket并verify。

5.3.7 Collision：fingerprint相等不是string相等

指纹碰撞（fingerprint collision）不可由modular hash完全消除。Two policies：

  • Monte Carlo：hash equal直接接受，速度稳定但有small false-positive probability。
  • Las Vegas：hash equal后逐字符check，结果永远正确；collision只增加时间。

官方当前代码描述为Las Vegas version。选择large random prime可让collision罕见，但independent result certificate仍应检查window equality。Security/adversarial input不能把普通rolling hash当cryptographic integrity proof；攻击者可构造collisions或触发大量verifications。

5.3.8 算法选择与真实成本

选择建议：

  • Short pattern、small one-off input：brute force，代码最小。
  • Repeated-prefix/adversarial guarantees、streaming：KMP failure/DFA。
  • Large alphabet natural language、pattern较长、random-access text：Boyer-Moore often skips well。
  • Multiple equal-length patterns、2D或fingerprint applications：Rabin-Karp。

Intrusion detection位于network choke point，通常同时搜索many patterns；production engines会进一步使用Aho-Corasick、vectorized search或specialized automata。本节四种single-pattern算法仍提供理解preprocessing、state reuse与certificate的基础。

Benchmark必须分开记录preprocess与search，报告characters compared、DFA memory、average skip、hash hits与collision verifications。只给wall-clock而不说明pattern reuse count，会让dense KMP或Boyer preprocessing得出误导结论。

5.3.9 Independent certificate与all-matches扩展

Leftmost search candidate offset k的验收：

  1. k等于not-found sentinel时，reference scan确认无match。
  2. 否则 (0\le k\le N-M)。
  3. text.substring(k,k+M)逐character等于pattern。
  4. text[0..k)中不存在更早full match。

这个validator与算法无关，能拒绝Rabin-Karp collision、Boyer skip过头、KMP restart过大或brute off-by-one。对very large text，测试oracle可只在CI小样本全扫；production result至少复核returned window和bounds。

All matches API还要定义overlap。Found at k后，naive next search若从k+M开始会漏overlapping matches；应从k+1继续，或让KMP接受state转到proper border。Result list需strictly increasing、每个window valid且相邻matches允许overlap。

5.3.10 逐步运行路线

先预测，再操作三个本节实验

分步1 / 3

1. 对象、操作与成本模型

先在“5.3 · Substring Search”的两个最小情境间切换，再逐项选择正式概念。预测“KMP 在 DFA/前缀函数预处理后搜索 Θ(N)；Rabin-Karp 以滚动散列常数时间更新窗口”在哪个前提下成立，并解释输入、操作和证书之间的关系。

Section model

5.3 · Substring Search：对象、操作与不变量

比较暴力、KMP、Boyer-Moore 与 Rabin-Karp 如何复用失败信息减少文本回退

选择最小情境

切换正式概念

输入合同操作证书algs4-5.3 · 先给前提，再执行，再验收当前概念：1/6
重叠模式
在 ABABABAC 中查找 ABABAC
当前观察
substring search：KMP 用已知前后缀继续，不重新比较已经确认的文本前缀
KMP 在 DFA/前缀函数预处理后搜索 Θ(N)；Rabin-Karp 以滚动散列常数时间更新窗口

本节易错边界与可重放合同

练习与答案

练习

问题 1：目录与状态映射。 对下列正式概念逐项指出正文解释、交互状态和练习证据：

  • 子字符串查找：在实验 1 中指出对应状态，并写出一个通过条件。
  • 暴力子字符串查找：在实验 2 中指出对应状态，并写出一个通过条件。
  • KMP算法：在实验 3 中指出对应状态，并写出一个通过条件。
  • Boyer-Moore算法：在实验 1 中指出对应状态，并写出一个通过条件。
  • Rabin-Karp算法：在实验 2 中指出对应状态，并写出一个通过条件。

问题 2：最小推演。 怎样证明“KMP 在 DFA/前缀函数预处理后搜索 Θ(N)；Rabin-Karp 以滚动散列常数时间更新窗口”不是孤立结论？

问题 3：故障恢复。 怎样证明“KMP 失配后错误地把文本指针和模式指针都回退，或 Rabin-Karp 命中哈希后不验字符”已经修复？

小结

  • Substring search在N-length text中寻找与M-length pattern相等的leftmost consecutive window。
  • Brute-force substring search每个alignment重启，worst case O(NM)，但实现简单。
  • Knuth-Morris-Pratt用border/restart state保留matched-prefix信息，text pointer不回退；dense DFA成本Theta(RM+N)。
  • Boyer-Moore从右向左比较，并以bad-character rightmost occurrence计算skip；官方版本不含strong good-suffix。
  • Rabin-Karp以rolling modular hash在constant work更新window，Las Vegas版本在hash hit后exact verify。
  • Independent certificate检查bounds、window equality与leftmost；algorithm internal state或fingerprint都不能替代最终证据。

资料与写作方式声明

本章以Algorithms, Fourth Edition的合法公开试读核定可见范围，并以目录限定未公开部分，并结合正文列出的技术资料独立重写；不宣称复现原书正文，也不沿用原作表述。

原作版权归作者与出版社所有；本站原创教学结构与表述仅供学习交流。

讨论

评论区加载中…