字符串匹配算法全景：从BM到AC自动机的演进之路
字符串匹配是计算机科学中最基础也最重要的问题之一。从文本编辑器的查找替换，到搜索引擎的全文检索，再到网络安全中的入侵检测与敏感词过滤，字符串匹配算法无处不在。本文系统梳理从朴素匹配到 AC 自动机的完整算法演进脉络，深入分析各算法的设计思想、预处理策略与工程适用场景。
问题定义与分类
字符串匹配问题的形式化定义如下：给定文本串 T（长度为 n）和模式串 P（长度为 m），在 T 中查找 P 出现的所有位置。
根据模式串的数量，字符串匹配问题可分为两类：
| 分类 | 描述 | 典型算法 |
|---|---|---|
| 单模式匹配 | 在文本串中查找一个模式串 | BF、BM、Horspool、Sunday、KMP、Rabin-Karp |
| 多模式匹配 | 在文本串中同时查找多个模式串 | AC 自动机、Wu-Manber |
单模式匹配算法又可按匹配方向进一步划分：
- 前缀匹配（从左到右）：KMP
- 后缀匹配（从右到左）：BM、Horspool
- 特定方向优化：Sunday（从左到右匹配，但利用窗口后一位字符跳转）
- 基于哈希：Rabin-Karp（不依赖字符逐一比较）
理解这一分类体系，是掌握各算法设计动机的前提。
朴素匹配算法（Brute Force）
朴素匹配是最直观的策略：将模式串与文本串逐位对齐，逐字符比较。一旦某个位置失配，模式串整体右移一位，重新从头比较。
文本串 T: A B C A B C A B D
模式串 P: A B C A B D
↑ 失配
文本串 T: A B C A B C A B D
模式串 P: A B C A B D
↑ 失配
... 逐位右移，重复比较
其核心逻辑可以用伪代码表示：
BruteForce(T, P):
for i = 0 to n - m:
for j = 0 to m - 1:
if T[i + j] != P[j]:
break
if j == m:
report match at position i
复杂度分析：最坏情况下，每次比较 m 个字符后失配，共需比较 (n - m + 1) 次，时间复杂度为 O(n * m)。典型的最坏用例是 T = "AAAAAAAAB"、P = "AAAAB"，每次比较到最后一位才失配。
朴素算法的核心缺陷在于：失配后丢弃了所有已匹配的信息，导致大量冗余比较。后续的所有优化算法，本质上都在解决同一个问题——如何利用已知信息，在失配时尽可能多地跳过无效比较。
基于后缀匹配的算法族
BM 算法：坏字符规则与好后缀规则
Boyer-Moore（BM）算法由 Robert S. Boyer 和 J Strother Moore 于 1977 年提出，是实际工程中应用最广泛的单模式匹配算法之一。Unix/Linux 系统中的 grep 命令在内部实现中即采用了 BM 算法的变体。
BM 算法的核心设计思想有两点：从右到左比较（后缀匹配），以及通过两条跳转规则最大化移动距离。
匹配方向
与朴素算法从左到右逐字符比较不同，BM 将模式串与文本串对齐后，从模式串的末尾开始向左比较。这一设计的直觉来源是：如果文本串中某个字符完全不出现在模式串中，从右侧发现这一点后可以直接跳过整个模式串长度，而从左侧发现则只能跳过一位。
坏字符规则（Bad Character Rule）
当从右向左比较过程中，文本串中某个字符 c 与模式串中对应位置的字符不匹配时，该字符 c 即为"坏字符"。此时按以下策略决定移动距离：
- 字符 c 不在模式串中出现：模式串直接跳过整个窗口，移动距离为当前比较位置到模式串起始位置的距离加一。
- 字符 c 在模式串中出现：将模式串向右滑动，使模式串中最右侧的字符 c 与文本串中的坏字符对齐。
文本串: ... X C B A B ...
模式串: A B C A B
↑ 比较位置 j=2, T 中字符为 'B'
'B' 在模式串中最右出现位置为 j=4
→ 但此时对齐会导致左移，取 1
坏字符规则实质：skip = j - last_occurrence(c)
若 skip <= 0，则至少移动 1 位
预处理阶段需要构建 MakeSkip 表（坏字符表），记录字符表中每个字符在模式串中最后一次出现的位置。未出现的字符标记为 -1。时间复杂度为 O(|Sigma| + m)，其中 |Sigma| 为字符集大小。
好后缀规则（Good Suffix Rule）
当从右到左比较的过程中，已经有若干字符匹配成功（形成"好后缀"），但在某个位置失配时，好后缀规则提供了另一种跳转策略。设好后缀为 t，则有三种情况：
情况一：模式串中存在另一个子串等于好后缀 t。 将模式串右移，使该子串与好后缀在文本串中的位置对齐。需要注意的是，该子串的前一个字符必须与好后缀前的字符不同，否则移动后仍会在同一位置失配。
模式串: C A B C A B
好后缀: A B
↑ 模式串中 CAB 的 AB 可以对齐
移动后: ... C A B C A B
情况二：模式串中没有完整的子串匹配好后缀，但模式串的某个前缀等于好后缀的某个后缀。 此时将模式串右移，使该前缀与好后缀的对应后缀对齐。
模式串: A B C D A B
好后缀: D A B
模式串前缀 AB = 好后缀后缀 AB
→ 将模式串的前缀 AB 与好后缀的后缀 AB 对齐
情况三：模式串中既无子串匹配好后缀，前缀也无法匹配好后缀的任何后缀。 此时模式串直接移动 m 位。
预处理阶段需要构建 MakeShift 表（好后缀表），记录每种好后缀情况下的移动距离。该表的构建较为复杂，通常借助后缀数组或前缀函数辅助完成，时间复杂度为 O(m)。
BM 的移动策略
每次失配时，BM 算法同时计算坏字符规则和好后缀规则给出的移动距离，取二者中的较大值作为实际移动距离。这是 BM 算法高效的关键——两条规则互相补充，确保了在各种情况下都能获得尽可能大的跳转。
复杂度分析：
| 场景 | 时间复杂度 | 说明 |
|---|---|---|
| 最好情况 | O(n / (m + 1)) | 每次比较第一个字符就跳过整个模式串 |
| 最坏情况 | O(n * m) | 退化为朴素匹配，如 T = "AAAA..."、P = "AAA" |
| 平均情况 | 亚线性 | 实际文本中表现优异，通常远快于 O(n) |
BM 算法在处理自然语言文本时尤为高效，因为坏字符规则在字符集较大时跳转距离更长。
Horspool 算法：BM 的工程化简化
Horspool 算法（1980）是 BM 算法的简化版本。它的核心观察是：BM 的好后缀规则实现复杂，而在实际应用中，坏字符规则已经能提供足够好的跳转效果。因此 Horspool 直接舍弃了好后缀规则，仅保留并改进了坏字符规则。
Horspool 的改进在于：始终以当前匹配窗口中文本串最末尾的字符作为坏字符参考，而非 BM 中以实际失配位置的字符作为参考。无论在哪个位置失配，都用窗口最右侧对应的文本字符来查表决定移动距离。
文本串: ... A B C D E F ...
模式串: X X X X
↑ 无论在哪失配，都以 D（窗口最末字符）查表
预处理：构建一个移动距离表，记录每个字符在模式串中距离最右端的距离。对于模式串 P[0..m-1]：
shift[c] = m （c 不在 P[0..m-2] 中出现）
shift[c] = m - 1 - max{j : P[j] = c, 0 <= j <= m-2} （c 在 P[0..m-2] 中出现）
注意最后一个字符 P[m-1] 不参与计算，因为它就是窗口末尾本身。
示例：模式串 P = "BARBER"，m = 6
| 字符 | B | A | R | E | 其他 |
|---|---|---|---|---|---|
| shift | 1 | 4 | 3 | 2 | 6 |
B 在位置 0 和 4 出现（排除最后位置 5），最右为位置 4，shift = 6 - 1 - 4 = 1。
Horspool 算法的最坏时间复杂度仍为 O(n * m)，但在实际应用中的平均性能与 BM 非常接近，且实现简洁得多，是许多工程场景下的首选。
Sunday 算法：面向实际场景的进一步优化
Sunday 算法由 Daniel M. Sunday 于 1990 年提出，从设计理念上看，它走了一条与 BM/Horspool 不同的路径：匹配方向从左到右（与朴素算法一致），但在失配时利用了一个独特的观察。
Sunday 的核心思想：当匹配失败时，不关注失配位置本身，而是关注文本串中参与当前匹配窗口的最末位字符的下一位字符，即 T[i + m]（i 为当前窗口起始位置）。
判断逻辑：
- T[i + m] 不在模式串中出现：模式串直接跳过 m + 1 位（因为包含该字符的任何对齐都不可能匹配）。
- T[i + m] 在模式串中出现：将模式串向右移动，使模式串中最右侧的该字符与 T[i + m] 对齐。
文本串: A B C E D A B C D
模式串: A B C D
↑ 失配（C != D）
关注 T[i+m] = T[4] = 'E'
'E' 不在模式串中 → 跳过 m+1 = 5 位
文本串: A B C E D A B C D
模式串: A B C D
→ 匹配成功
预处理：与 Horspool 类似，构建一个移动距离表。不同的是，Sunday 的表需要包含模式串的最后一个字符（因为参考的是窗口外的下一个字符）：
shift[c] = m + 1 （c 不在 P 中出现）
shift[c] = m - max{j : P[j] = c, 0 <= j <= m-1} （c 在 P 中出现）
Sunday 算法的优势在于最大跳转距离为 m + 1（比 BM 的 m 还多一位），且实现极其简洁。在短模式串和字符集较大的场景下（如英文文本搜索），Sunday 通常表现最优。但在最坏情况下（如二进制文本中搜索重复模式），其复杂度同样退化为 O(n * m)。
后缀匹配算法族小结
| 算法 | 匹配方向 | 跳转依据 | 预处理复杂度 | 实现复杂度 |
|---|---|---|---|---|
| BM | 右→左 | 坏字符 + 好后缀 | O(|Sigma| + m) | 较高 |
| Horspool | 右→左 | 窗口末尾字符 | O(|Sigma| + m) | 低 |
| Sunday | 左→右 | 窗口下一位字符 | O(|Sigma| + m) | 最低 |
三者的共性是：都通过预处理模式串，在失配时尽可能地跳过更多的比较位置。差异在于跳转参考字符的选取策略和实现复杂度之间的权衡。
基于前缀匹配的算法
KMP 算法：部分匹配表与无回溯匹配
Knuth-Morris-Pratt（KMP）算法由 Donald Knuth、James Morris 和 Vaughan Pratt 于 1977 年提出，与 BM 算法同年发表，但走了一条完全不同的技术路线。KMP 的设计目标非常明确：文本串指针永远不回溯。
在朴素算法中，每次失配后文本串指针要退回到本次匹配开始位置的下一位。KMP 的核心洞察是：当在位置 j 处失配时，模式串的前 j 个字符（P[0..j-1]）已经与文本串匹配成功。如果 P[0..j-1] 自身存在"前缀等于后缀"的结构，那么可以直接将模式串滑动到该前缀位置继续比较，而无需回退文本串指针。
next 数组（部分匹配表）
next 数组（也称失败函数或部分匹配表）是 KMP 算法的核心数据结构。对于模式串 P，next[j] 的含义是：P[0..j-1] 这个子串中，最长的"真前缀等于真后缀"的长度。
以模式串 P = "ABCABD" 为例：
| j | 子串 | 最长公共前后缀 | next[j] |
|---|---|---|---|
| 0 | "" | 无 | -1（特殊标记） |
| 1 | "A" | 无 | 0 |
| 2 | "AB" | 无 | 0 |
| 3 | "ABC" | 无 | 0 |
| 4 | "ABCA" | "A" | 1 |
| 5 | "ABCAB" | "AB" | 2 |
next 数组的构建过程
next 数组的构建本身就是一次"模式串对自身的匹配"过程，其思想与 KMP 匹配过程完全一致：
BuildNext(P):
m = length(P)
next[0] = -1
j = 0, k = -1
while j < m - 1:
if k == -1 or P[j] == P[k]:
j++, k++
next[j] = k
else:
k = next[k] // 利用已计算的 next 值回溯
这段逻辑的关键在于 k = next[k] 这一步。当 P[j] 与 P[k] 不匹配时，不是简单地将 k 重置为 0，而是利用 next 数组已经计算好的部分，跳转到下一个可能匹配的位置。这正是 KMP 思想在预处理阶段的自我应用。
构建过程的时间复杂度为 O(m)，因为 j 单调递增且 k 的回退次数有上界。
匹配过程
KMP_Match(T, P):
i = 0, j = 0
while i < n and j < m:
if j == -1 or T[i] == P[j]:
i++, j++
else:
j = next[j] // 文本串指针 i 不回溯
if j == m:
report match at position i - m
匹配过程中，文本串指针 i 始终向前移动，永不回溯。每次失配时，仅调整模式串指针 j 到 next[j] 的位置，相当于将模式串向右滑动 j - next[j] 位。
复杂度分析：
| 阶段 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 预处理（构建 next） | O(m) | O(m) |
| 匹配 | O(n) | - |
| 总计 | O(n + m) | O(m) |
KMP 的时间复杂度是严格的 O(n + m)，不存在退化为 O(n * m) 的最坏情况，这是它相对于 BM 系列算法的理论优势。然而在实际工程中，BM 及其变体在大字符集文本上的平均表现往往优于 KMP，因为 BM 的跳转距离通常更大。
next 数组的优化
标准 next 数组存在一个可优化的场景：当 P[j] 失配后跳转到 next[j] = k，若 P[k] == P[j]，则在位置 k 必然还会失配，这次跳转是浪费的。优化版本在构建时做如下修正：
if P[j] == P[k]:
next[j] = next[k] // 跳过必然失败的比较
else:
next[j] = k
该优化不改变渐进复杂度，但能减少实际比较次数。
基于哈希的匹配
Rabin-Karp 算法：滚动哈希
Rabin-Karp（RK）算法由 Michael Rabin 和 Richard Karp 于 1987 年提出，采用了一种与上述算法截然不同的思路：不逐字符比较，而是比较哈希值。
基本思想
将模式串 P 计算出一个哈希值 h(P)，然后对文本串 T 中每个长度为 m 的子串计算哈希值，与 h(P) 比较。若哈希值相等，再逐字符验证以排除哈希冲突。
朴素地实现这一思想，每个子串的哈希计算需要 O(m) 时间，总复杂度仍为 O(n * m)，并无改善。RK 算法的精妙之处在于滚动哈希（Rolling Hash）。
滚动哈希
选取一个基数 d（通常取字符集大小）和一个素数 q（用于取模防止溢出），定义哈希函数：
h(S[i..i+m-1]) = (S[i] * d^(m-1) + S[i+1] * d^(m-2) + ... + S[i+m-1]) mod q
当窗口从 T[i..i+m-1] 滑动到 T[i+1..i+m] 时，新哈希值可以通过 O(1) 的算术运算从旧值递推得出：
h(T[i+1..i+m]) = (d * (h(T[i..i+m-1]) - T[i] * d^(m-1)) + T[i+m]) mod q
即：移除最高位字符的贡献，整体左移一位（乘以 d），加上新进入窗口的字符。整个过程仅涉及常数次乘法、加法和取模运算。
哈希冲突处理
当 h(T[i..i+m-1]) == h(P) 时，存在两种可能：真正匹配，或哈希冲突。因此必须进行逐字符验证。选择合适的素数 q 可以降低冲突概率。在理论分析中，若 q 足够大且随机选取，冲突概率为 O(1/q)。
复杂度分析：
| 场景 | 时间复杂度 | 说明 |
|---|---|---|
| 期望情况 | O(n + m) | 冲突次数少，验证开销可忽略 |
| 最坏情况 | O(n * m) | 所有窗口哈希均冲突（如 q 选择不当） |
RK 的独特优势
RK 算法在单模式匹配中并不比 BM/KMP 更优，但它有一个独特的应用场景：多模式串的同时匹配。当需要在文本中同时搜索 k 个等长的模式串时，可以将所有模式串的哈希值存入哈希表，每次窗口滑动后查表比较，时间复杂度为 O(n + k * m)，远优于逐一匹配。此外，RK 算法天然适合二维模式匹配（在矩阵中搜索子矩阵）等扩展场景。
多模式匹配
AC 自动机：Trie + 失败指针
前面讨论的算法都针对单模式匹配问题。当需要在一个文本串中同时搜索多个模式串时（如敏感词过滤需要同时检测数千个关键词），逐一应用单模式算法的效率极低。Aho-Corasick（AC）自动机正是为解决这一问题而设计的。
AC 自动机由 Alfred Aho 和 Margaret Corasick 于 1975 年提出，是多模式匹配的经典算法。其核心思想是将多个模式串构建为一个有限状态自动机，使文本串只需扫描一遍即可找到所有模式串的所有出现位置。
三个核心函数
AC 自动机由三个函数协同工作：
1. goto 函数（转移函数）
goto 函数本质上是一棵 Trie 树（字典树），由所有模式串构建而成。Trie 的每条边代表一个字符，从根节点到某个节点的路径表示某个模式串的前缀。
以模式串集合 {"he", "she", "his", "hers"} 为例，构建的 Trie 结构如下：
root
/ \
h s
/ \ \
e i h
| | |
r s e
|
s
goto(s, c) 表示在状态 s 下输入字符 c 后转移到的下一个状态。若当前状态没有字符 c 对应的子节点，则 goto 返回失败（fail）。根节点是特殊的：对于根节点，任何不匹配的字符都转移回根节点本身（而非失败），这保证了自动机始终可以继续运行。
2. failure 函数（失败指针）
failure 函数是 AC 自动机的精髓所在，其设计理念与 KMP 的 next 数组一脉相承。当在某个状态 s 下无法通过 goto 函数继续前进时，failure(s) 指向另一个状态 s'，使得从根到 s' 的路径所代表的字符串是从根到 s 的路径所代表的字符串的最长真后缀，且 s' 是 Trie 中的一个有效状态。
直观理解：failure 指针利用了"已匹配部分的后缀可能是另一个模式串的前缀"这一信息，避免了文本串指针的回溯。
以上例为例，部分 failure 指针：
- 状态 "sh" 的 failure 指向状态 "h"（因为 "h" 是 "sh" 的最长真后缀且在 Trie 中存在）
- 状态 "she" 的 failure 指向状态 "he"（因为 "he" 是 "she" 的最长真后缀且在 Trie 中存在）
3. output 函数（输出函数）
output(s) 记录在状态 s 处可以报告的所有匹配模式串。一个状态可能对应多个输出，因为到达某个状态时，不仅该状态本身可能对应一个完整的模式串，其 failure 链上的祖先状态也可能对应完整的模式串。
例如，到达状态 "she" 时，output 不仅包含 "she"，还需沿 failure 链检查：failure("she") = "he"，而 "he" 也是一个完整模式串，因此 output("she") = {"she", "he"}。
构建过程
AC 自动机的构建分为两个阶段：
阶段一：构建 Trie 树（goto 函数 + 初始 output 函数）
将所有模式串逐一插入 Trie 树。每插入一个完整的模式串后，在其终止节点的 output 集合中记录该模式串。时间复杂度为 O(所有模式串总长度之和)。
阶段二：BFS 构建 failure 指针（同时完善 output 函数）
使用广度优先搜索（BFS）逐层计算 failure 指针：
BuildFailure():
queue = new Queue()
// 第一层节点的 failure 指向根
for each child c of root:
failure(c) = root
queue.enqueue(c)
// BFS 逐层构建
while queue is not empty:
current = queue.dequeue()
for each child node via character a:
// 核心逻辑：沿 failure 链找可行转移
state = failure(current)
while state != root and goto(state, a) == fail:
state = failure(state)
failure(child) = goto(state, a) // 若 goto(root, a) 也 fail，则为 root
// 合并 output：当前节点的 output 需包含 failure 指向节点的 output
output(child) = output(child) ∪ output(failure(child))
queue.enqueue(child)
BFS 保证了在计算某个节点的 failure 指针时，其所有更浅层节点的 failure 指针已经计算完成。合并 output 的操作保证了匹配过程中不会遗漏任何模式串。
匹配过程
AC_Match(T):
state = root
for i = 0 to n - 1:
while state != root and goto(state, T[i]) == fail:
state = failure(state)
state = goto(state, T[i])
if state == fail:
state = root
// 报告当前状态的所有匹配
temp = state
while temp != root:
if output(temp) is not empty:
report output(temp) at position i
temp = failure(temp)
文本串的每个字符只被读取一次，指针始终向前。对于每个位置，沿 failure 链检查所有可能的匹配输出。
复杂度分析：
| 阶段 | 时间复杂度 | 说明 |
|---|---|---|
| 构建 Trie | O(L) | L 为所有模式串总长度之和 |
| 构建 failure | O(L) | BFS 遍历所有节点 |
| 匹配 | O(n + z) | n 为文本长度，z 为匹配结果总数 |
| 空间 | O(L * |Sigma|) | 可通过链表或哈希优化 |
工程应用场景
AC 自动机在工业界有广泛的应用：
- 敏感词过滤：将敏感词库构建为 AC 自动机，对用户输入文本进行一次扫描即可检出所有敏感词。典型的敏感词库包含数万个词条，使用 AC 自动机可以在毫秒级完成检测。
- 病毒特征码扫描：杀毒软件将病毒特征码库构建为 AC 自动机，扫描文件时一次遍历即可匹配所有已知特征。
- 网络入侵检测系统（IDS）：如 Snort，利用 AC 自动机在网络数据包中实时检测攻击特征。
- 搜索引擎：对查询词进行多关键词高亮标注。
- DNA 序列分析：在基因组序列中搜索多个目标片段。
算法选型指南
字符串匹配算法的选型不存在"银弹"，需要根据具体场景的特征进行权衡：
复杂度对比
| 算法 | 预处理时间 | 匹配时间（最优） | 匹配时间（最差） | 空间 | 适用场景 |
|---|---|---|---|---|---|
| Brute Force | 无 | O(n) | O(n * m) | O(1) | 极短模式串、一次性匹配 |
| BM | O(|Sigma| + m) | O(n / m) | O(n * m) | O(|Sigma| + m) | 长文本、大字符集 |
| Horspool | O(|Sigma| + m) | O(n / m) | O(n * m) | O(|Sigma|) | BM 的工程简化替代 |
| Sunday | O(|Sigma| + m) | O(n / (m+1)) | O(n * m) | O(|Sigma|) | 短模式串、交互式搜索 |
| KMP | O(m) | O(n) | O(n) | O(m) | 需要最坏保证的场景 |
| Rabin-Karp | O(m) | O(n) | O(n * m) | O(1) | 多模式等长匹配、二维匹配 |
| AC 自动机 | O(L) | O(n + z) | O(n + z) | O(L * |Sigma|) | 多模式匹配 |
场景决策路径
单模式短文本（m 较小，n 较小）：朴素算法或 Sunday 算法。预处理开销在短文本上不划算，Sunday 的实现简单且跳转距离大。
单模式长文本（大字符集，如自然语言）：BM 算法或 Horspool 算法。大字符集意味着坏字符规则的跳转距离更大，BM 系列算法的亚线性性能优势最为明显。Linux 的 grep 正是基于这一判断选择了 BM 变体。
单模式长文本（小字符集，如 DNA 序列）：KMP 算法。小字符集下 BM 系列的跳转距离有限，KMP 的 O(n) 最坏保证更有价值。
需要严格最坏复杂度保证：KMP 算法。在安全相关场景中（如正则表达式引擎的实现），算法的最坏性能不可接受为 O(n * m)，此时 KMP 是唯一的选择。
多个等长模式串：Rabin-Karp 算法。通过哈希表存储所有模式串的哈希值，一次滚动扫描即可完成。
大规模多模式匹配：AC 自动机。模式串数量从几十到数万，AC 自动机的匹配时间与模式串数量无关（仅与文本长度和匹配结果数相关），是唯一可行的方案。
工程实践中的补充考量
算法选择不仅取决于渐进复杂度，还需考虑以下工程因素：
- 缓存友好性：BM/Horspool 的跳跃式访问模式对 CPU 缓存不太友好，KMP 的顺序访问模式在某些场景下可能因缓存命中率更高而表现更好。
- 预处理开销：如果文本很短或匹配只执行一次，预处理的固定开销可能超过它带来的收益。此时朴素算法反而最优。
- 实现复杂度与可维护性：BM 的完整实现（包括好后缀规则）相当复杂，Horspool 和 Sunday 在牺牲极少理论性能的前提下大幅降低了实现难度。
- 并行化潜力：Rabin-Karp 的哈希计算具有天然的可并行性，适合 GPU 或 SIMD 加速。
字符串匹配算法的演进史，实质上是一部信息利用效率的进化史。从朴素算法的"零信息利用"，到 KMP/BM 的"利用已匹配字符信息"，再到 AC 自动机的"利用多模式串间的共享前缀信息"，每一步跨越都建立在对问题结构更深入的理解之上。理解这些算法的设计思想，远比记忆它们的具体实现更有价值。