第 11 章：搜索与字符串匹配
元数据卡
| 属性 | 值 |
|---|---|
| 难度 | （进阶型） |
| 前置 | 第 5 章（二叉树/BST）、递归与分治思想 |
| 关键词 | 二分搜索·边界条件·三分搜索·旋转数组·Rabin-Karp·滚动哈希·KMP·Partial Match Table·Trie·前缀树·字符串匹配 |
| 预计阅读 | 110 分钟 |
| 代码行 | ~240 行（三语言合计） |
你在哪
在森林里找一样东西——如果不是直接知道位置（哈希表）、也不是按顺序排好的（BST）——你还能怎么办？二分法、字符串匹配——老陈说的"在干草堆里找针"就是这样。
前两章你成了排序大师。数组中的元素被你整得服服帖帖——想怎么排就怎么排。但排序本身只是手段，你真正的目的是找到东西。
想象一个场景：你在驿站找到了一本前人的冒险者笔记，里面按顺序记录了森林里所有石碑上的冒险者排名——总共十亿条。你要找「林间行者」——排名最高的冒险者之一。你不可能一条一条翻，你会对半翻，再对半翻，再对半翻……这就是二分搜索的精髓。
但更棘手的情况来了。笔记里的记录没排序？只有部分排序？甚至你要在一段林间日志全文里找一个名字——比如在厚厚的冒险日志里找「火焰行者」出现了多少次？
这一章解决的就是这个问题：如何在不同的数据形态中高效定位目标。从最经典的二分搜索和它的各种边界变体，到字符串匹配领域的三大神器：Rabin-Karp（哈希）、KMP（自动机）、Trie（前缀树）。
你的任务
本章分层
- 必读：二分搜索（标准版、左边界、右边界）；简单的字符串匹配（暴力或 Rabin-Karp 的直觉）
- 选读：旋转数组中的二分搜索；Trie 树（前缀树）的插入、搜索、前缀匹配
- 深水区：KMP 算法的 Partial Match Table 构建与匹配过程；三分搜索（连续函数极值）
本章不会要求你掌握
- KMP 的完整实现——理解核心思想（text 指针不回退）即可
- Trie 树的 delete 操作
- BM 算法、Suffix Array 等高级字符串匹配
读完本章，你应当能：
- 不假思索地写出二分搜索——以及它的左边界、右边界版本
- 处理旋转数组：在「断开」的有序数组中寻找目标
- 了解简单的字符串匹配（暴力法和 Rabin-Karp 的滚动哈希直觉）
- （选）实现 Trie 树的插入、搜索、前缀匹配三种操作
- （选）理解 KMP 的核心思想：text 指针从不回头
遭遇战→获得技能
① 二分搜索（Binary Search）—— 区间切割的艺术
核心直觉：每次排除一半。 你不是在遍历，你是在收缩区间。
最朴素的二分——在有序数组中找一个值，存在返回索引，不存在返回 -1：
def binary_search(arr, target):
"""标准二分搜索——寻找 target 在有序数组中的位置"""
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2 # 防溢出写法
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# 试运行
arr = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search(arr, 7)) # → 3
print(binary_search(arr, 10)) # → -1代码只有几行，但 90% 的人第一次会写错。 错在哪里？无外乎这几个地方：
while left <= right还是while left < right？right = mid - 1还是right = mid？mid = left + (right - left) // 2在 Python 里无所谓，但在 Java/C++ 里(left + right) // 2如果 left+right 超过 int 最大值就会溢出。养成用减法的习惯。
这组问题背后是一个深刻的事实：二分搜索不是一种算法，而是一类算法。不同的边界条件和搜索目标，你会写出不同的二分。
1.1 左边界二分 —— 找到第一个 ≥ target 的位置
def binary_search_leftmost(arr, target):
"""寻找第一个 ≥ target 的索引（C++ lower_bound）"""
left, right = 0, len(arr) # 注意 right = len(arr)，不是 len-1
while left < right: # 左闭右开区间
mid = left + (right - left) // 2
if arr[mid] < target:
left = mid + 1
else:
right = mid
return left # 返回时 left == right
arr = [1, 2, 4, 4, 4, 5, 6]
print(binary_search_leftmost(arr, 4)) # → 2 （第一个 4 的位置）
print(binary_search_leftmost(arr, 7)) # → 7 （超出范围，arr[7] 不存在）
print(binary_search_leftmost(arr, 0)) # → 01.2 右边界二分 —— 找到最后一个 ≤ target 的位置
def binary_search_rightmost(arr, target):
"""寻找最后一个 ≤ target 的索引"""
left, right = 0, len(arr)
while left < right:
mid = left + (right - left) // 2
if arr[mid] > target:
right = mid
else:
left = mid + 1
return left - 1 # left 停在了第一个 > target 的位置
arr = [1, 2, 4, 4, 4, 5, 6]
print(binary_search_rightmost(arr, 4)) # → 4 （最后一个 4 的位置）
print(binary_search_rightmost(arr, 5)) # → 5为什么 rightmost 比 leftmost 多了个 return left - 1？
因为左边界版本的 arr[mid] < target → left = mid + 1 直接定位 target 的第一个出现。而右边界版本我们要找「最后一个 ≤ target」，当 arr[mid] <= target 时我们收缩 left = mid + 1——这一步把 left 推过了正确位置，所以返回前要回退一格。
** Java 差异：** Java 没有
lower_bound和upper_bound这样的标准库。你需要手写：javaint lowerBound(int[] arr, int target) { int left = 0, right = arr.length; while (left < right) { int mid = left + (right - left) / 2; if (arr[mid] < target) left = mid + 1; else right = mid; } return left; }
** C++ 差异：** C++ 标准库直接提供了
std::lower_bound和std::upper_bound，你的工作不是实现它，是用对它们：cpp`vector<int> v = {1, 2, 4, 4, 4, 5, 6};` auto it = lower_bound(v.begin(), v.end(), 4); auto it2 = upper_bound(v.begin(), v.end(), 4); int first4 = it - v.begin(); // 2 int after4 = it2 - v.begin(); // 5
② 搜索旋转数组 —— 有序断开后怎么找？
题目来了：一个有序数组在某个未知点被旋转了，比如
[0,1,2,4,5,6,7]变成了[4,5,6,7,0,1,2]。给你这个旋转后的数组和一个 target，找到它的位置。要求 O(log n)。
核心洞察：数组被分成两段，总有一半是严格有序的——要么左半，要么右半。我们就利用这一半来判断 target 在哪。
def search_rotated(arr, target):
"""在旋转有序数组中搜索 target（无重复元素）"""
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
# 左半部分有序
if arr[left] <= arr[mid]:
if arr[left] <= target < arr[mid]:
right = mid - 1
else:
left = mid + 1
# 右半部分有序
else:
if arr[mid] < target <= arr[right]:
left = mid + 1
else:
right = mid - 1
return -1
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0)) # → 4
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 3)) # → -1数组旋转的几种情况
[4, 5, 6, 7, 0, 1, 2]
↑ ↑ ↑
左半有序部分 右半有序部分
[4..7] [0..2]
情况1: target=0 → 不在左半(mid=7, arr[left]=4 ≤ target=0? 不成立) → 去右半
情况2: target=5 → 左半搜索 (arr[left]=4 ≤ 5 < mid=7) → 收缩 right延伸：有重复元素怎么办？
当 arr[left] == arr[mid] == arr[right] 时，你无法判断哪半有序——例如 [1, 1, 1, 1, 1, 1, 0, 1, 1]。退化场景下只能逐个排除，最坏 O(n)：
def search_rotated_with_duplicates(arr, target):
"""旋转数组搜索（允许重复）"""
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return True
# 左右中三值相等 → 退化为线性缩进
if arr[left] == arr[mid] == arr[right]:
left += 1
right -= 1
continue
if arr[left] <= arr[mid]:
if arr[left] <= target < arr[mid]:
right = mid - 1
else:
left = mid + 1
else:
if arr[mid] < target <= arr[right]:
left = mid + 1
else:
right = mid - 1
return False附录：三分搜索（Ternary Search）—— 适用于连续函数极值
三分搜索在离散数组中用处不大，仅在连续函数极值搜索中有用。这里作为附录，需要时再回来看。
核心直觉：同时取两个中间点，比较后砍掉 1/3。 适用于单峰函数（先升后降或先降后升）找极值。
三分搜索在离散数组中用处不大（二分已经够好），但在连续函数的极值搜索中有一席之地。比如找 f(x) = -x² + 5x + 10 的最大值。
def ternary_search(f, left, right, eps=1e-7):
"""三分搜索找单峰函数极值（f 为凸函数时找最大值）"""
while right - left > eps:
m1 = left + (right - left) / 3
m2 = right - (right - left) / 3
if f(m1) < f(m2):
left = m1 # f(m2) 更大 → 极值在右半
else:
right = m2 # f(m1) 更大 → 极值在左半
return (left + right) / 2 # 返回极值点
def f(x):
return -(x ** 2) + 5 * x + 10
max_x = ternary_search(f, -10, 10)
print(f"最大值在 x ≈ {max_x:.4f}, f(x) = {f(max_x):.4f}")
# → 最大值在 x ≈ 2.5000, f(x) = 16.2500为什么不用三分的「数组版」找有序数组中的目标？
因为数组的搜索中，一次三分做两次比较但只排除 1/3 元素，而二分做一次比较排除一半。数学上：
- 二分：log₂n 次比较
- 三分：2 × log_(3/2)n ≈ 2 × 1.7 × log₂n = 3.4 × log₂n 次比较
三分要多做 3.4 倍的工作。所以离散搜索用二分，连续极值才用三分。
④ Rabin-Karp —— 滚动哈希让字符串匹配跑起来
问题：给定一段文本
text（长度 n）和一个模式pattern（长度 m），找出 pattern 在 text 中的所有出现位置。
暴力法是每个位置逐字符比较——O(n×m)。Rabin-Karp 的思路是：别比字符了，比哈希值。
def rabin_karp(text, pattern):
"""Rabin-Karp 字符串匹配——滚动哈希"""
n, m = len(text), len(pattern)
if m > n or m == 0:
return []
base = 256 # 字符集大小（ASCII 够了）
mod = 10**9 + 7 # 大质数，减少哈希冲突
result = []
# 计算 pattern 的哈希值和 base^(m-1) 的余数
# 这两个值在整个过程中只算一次
pat_hash = 0
top_val = 1
for i in range(m):
pat_hash = (pat_hash * base + ord(pattern[i])) % mod
for i in range(m - 1):
top_val = (top_val * base) % mod
# 计算 text 第一个窗口的哈希
txt_hash = 0
for i in range(m):
txt_hash = (txt_hash * base + ord(text[i])) % mod
# 滚动比较
for i in range(n - m + 1):
if pat_hash == txt_hash:
# 哈希匹配但可能有冲突，二次校验
if text[i:i + m] == pattern:
result.append(i)
# 滚动：移除前一个字符，加入后一个字符
if i < n - m:
txt_hash = (txt_hash - ord(text[i]) * top_val) % mod
txt_hash = (txt_hash * base + ord(text[i + m])) % mod
txt_hash %= mod
return result
text = "AABAACAADAABAAABAA"
pattern = "AABA"
print(rabin_karp(text, pattern)) # → [0, 9, 13]核心逻辑——滚动哈希是怎么「滚」的？
假设 text = "AAB"，它的哈希值是：ord('A')×base² + ord('A')×base + ord('B')。
现在要向右移一位，变成 text[1:4] = "ABA"：
- 移除
ord('A') × base²的贡献 - 整体左移一位（乘以 base）
- 加入
ord('A')（新窗口的最后一个字符）
这整个过程是 O(1) 的——不重新扫描 m 个字符。这就是「滚动」的含义。
哈希冲突怎么办？ 上述代码已经处理了：哈希相等时不立即返回，而是做一次 text[i:i+m] == pattern 的字符级校验。如果模数选得好，冲突极少，整体复杂度接近 O(n+m)。
什么时候 Rabin-Karp 会退化？ 文本和 pattern 高度相似时——比如全部是同一个字符——每次哈希都相等，等于退化回逐个比较，O(n×m)。但概率极低。
KMP（Knuth-Morris-Pratt）—— 不让指针往回走（进阶选读）
KMP 是字符串匹配的经典算法，但面试和工程中直接手写的机会不多。 主线先掌握二分搜索和 Rabin-Karp 的直觉即可。理解 KMP 的核心思想（text 指针不回退）比记忆代码更重要。
暴力匹配最让人心疼的地方：当匹配到
text = "AAAB...", pattern = "AAAA"时，你在第四个字符碰壁了，然后暴力法乖乖把 pattern 往后挪一位，重新开始。但你已经知道 text 的前三个字符是 'A' 了，为什么不利用这个信息？
KMP 的核心思想：模式串自己知道该怎么「退」——不需要 text 指针回溯。
5.1 Partial Match Table（也叫 next 数组 / 失配函数）
先看一个表。
对于 pattern = "ABABAC"，PMT 长这样：
字符: A B A B A C
PMT: 0 0 1 2 3 0解释：PMT[i] = 「pattern[0:i] 这个前缀中，最长的相等前缀-后缀的长度」。
- i=0, "A"：没有真前后缀 → 0
- i=1, "AB"：前缀 {A}，后缀 {B} → 无匹配 → 0
- i=2, "ABA"：前缀 {A, AB}，后缀 {BA, A} → A 匹配 → 1
- i=3, "ABAB"：前缀 {A, AB, ABA}，后缀 {BAB, AB, B} → AB 匹配 → 2
- i=4, "ABABA"：前缀 {A, AB, ABA, ABAB}，后缀 {BABA, ABA, BA, A} → ABA 匹配 → 3
- i=5, "ABABAC"：前缀 {A, AB, ABA, ABAB, ABABA}，后缀 {BABAC, ABAC, BAC, AC, C} → 无匹配 → 0
手工推 PMT 的技巧：算出来 PMT[i] 后，算 PMT[i+1] 时先看 pattern[i+1] 能否和已有的最长前缀的下一个字符匹配。能就直接 +1，不能就回退到前一个更短的前缀——有点像 KMP 自己对自己做 KMP。
def build_pmt(pattern):
"""构建 Partial Match Table（next 数组）"""
m = len(pattern)
pmt = [0] * m
j = 0 # 当前最长匹配前缀的长度
for i in range(1, m):
# 当不匹配时，j 回退到前一个 PMT 位置
while j > 0 and pattern[i] != pattern[j]:
j = pmt[j - 1]
if pattern[i] == pattern[j]:
j += 1
pmt[i] = j
return pmt
print(build_pmt("ABABAC")) # → [0, 0, 1, 2, 3, 0]5.2 KMP 主流程 —— 拿着 PMT 匹配文本
def kmp_search(text, pattern):
"""KMP 字符串匹配——text 指针从不回头"""
n, m = len(text), len(pattern)
if m == 0:
return []
if m > n:
return []
pmt = build_pmt(pattern)
result = []
j = 0 # pattern 的当前匹配位置
for i in range(n):
# 不匹配 → j 通过 PMT 回退
while j > 0 and text[i] != pattern[j]:
j = pmt[j - 1]
if text[i] == pattern[j]:
j += 1
if j == m:
result.append(i - m + 1)
# 找到后继续找下一个（重叠匹配也允许）
j = pmt[j - 1]
return result
text = "ABABABACABA"
pattern = "ABABAC"
print(kmp_search(text, pattern)) # → [2]
print(kmp_search("AAAAA", "AA")) # → [0, 1, 2, 3]KMP 的可视化运行
text: A B A B A B A C A B A
pattern: A B A B A C
0 1 2 3 4 5
✓ ✓ ✓ ✓ ✓ ✗ ← i=5 处 text[5]=B ≠ pattern[5]=C
暴力法：text 指针回退到 1，pattern 从头开始
KMP： text 指针停在 5，利用 PMT[4]=3 将 j 跳到 3
重新比较 text[5]=B 和 pattern[3]=B → ✓
j=3这就是 KMP 的浪漫之处：text 指针永远向前，犯过的错只靠 pattern 自己消化。
** Java 差异：** Java 的
String.indexOf()用的是暴力法——对短字符串来说，KMP 的 PMT 构建开销反而更贵。JDK 的开发者做了权衡：
- 短串（最常见场景）：暴力法 O(n×m) 但常数极小
- 长串、重复模式：才是 KMP 发挥了优势
Trie（前缀树 / 字典树）—— 共享前缀的自动补全引擎
Trie 是字符串查找的实用数据结构。 建议先掌握主线再回来看。
问题：给你 10⁵ 个单词，要求实现一个 API：输入前缀，返回所有匹配单词。或者——判断某个单词是否存在于字典中。
问题：给你 10⁵ 个单词，要求实现一个 API：输入前缀，返回所有匹配单词。或者——判断某个单词是否存在于字典中。
HashSet 可以回答「单词是否存在」，但回答不了「以 abc 开头」的问题。Trie 就是为此而生的一棵树。
class TrieNode:
def __init__(self):
self.children = {} # 字符 → TrieNode
self.is_end = False # 是否是某个单词的结尾
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
"""插入一个单词"""
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def search(self, word: str) -> bool:
"""精确搜索：单词是否完整存在"""
node = self._find_node(word)
return node is not None and node.is_end
def starts_with(self, prefix: str) -> bool:
"""前缀搜索：是否存在以 prefix 开头的单词"""
return self._find_node(prefix) is not None
def _find_node(self, prefix: str) -> TrieNode | None:
"""辅助：沿前缀行走，返回最后一个节点"""
node = self.root
for ch in prefix:
if ch not in node.children:
return None
node = node.children[ch]
return node
def autocomplete(self, prefix: str) -> list[str]:
"""自动补全：返回所有以 prefix 开头的单词"""
node = self._find_node(prefix)
if node is None:
return []
results = []
self._dfs(node, prefix, results)
return results
def _dfs(self, node: TrieNode, path: str, results: list[str]):
"""深度优先收集所有单词"""
if node.is_end:
results.append(path)
for ch, child in node.children.items():
self._dfs(child, path + ch, results)
# 试运行
trie = Trie()
words = ["apple", "app", "application", "appetite", "banana"]
for w in words:
trie.insert(w)
print(trie.search("app")) # → True
print(trie.search("appl")) # → False（不是完整单词）
print(trie.starts_with("app")) # → True
print(trie.autocomplete("app"))
# → ['app', 'apple', 'appetite', 'application']Trie 的结构图（"app", "apple", "banana"）
root
/ \
a b
/ \
p a
/ \
p n
/ \ \
$ l a
| \
e n
| \
$ a
\
$
（$ 标记 is_end = True）Trie 的时间复杂度
| 操作 | 时间 | 空间 |
|---|---|---|
| 插入 | O(m) | O(总字符数 × 字符集大小) |
| 搜索 | O(m) | — |
| 前缀匹配 | O(m) | — |
| 自动补全 | O(m + 结果数) | — |
m = 单词长度。所有操作都和字典大小无关——这就是 Trie 性感的地方。
空间问题：每个节点存一个 children 字典（或数组），在字符集大时（比如 Unicode）内存爆炸。工程上的优化方案：
- Radix Tree / Patricia Trie：把只有一个孩子的链压缩成一条边
- Double-array Trie：用两个数组表示，内存紧凑（AC 自动机的常用底层）
** C++ 差异：** 用数组实现 children 更高效（假设仅小写字母）：
cppstruct TrieNode { TrieNode* children[26]; bool isEnd; TrieNode() : isEnd(false) { fill(begin(children), end(children), nullptr); } };优点：O(1) 的子节点查找，无哈希开销。缺点：每个节点固定占 26 个指针空间（208 字节）。
常见陷阱
二分搜索为什么「只有 10% 的人能一次性写对」？
写二分，本质上是在回答三个问题：
- 搜索空间是什么？ 左闭右闭
[left, right]还是左闭右开[left, right)？ - 收缩规则是什么？ 找到 target 时返回；没找到时排除 mid 还是保留 mid？
- 终止状态是什么？ left > right 还是 left == right？
如果你用左闭右闭，就用 <=，right = mid - 1。如果用左闭右开，就用 <，right = mid。混用一定会错。
Rabin-Karp vs KMP vs Trie：什么时候用哪个？
| 适用场景 | 复杂度 | 特点 | |
|---|---|---|---|
| Rabin-Karp | 单模式匹配，长文本 | O(n+m) 平均 | 简单，哈希冲突退化 |
| KMP | 单模式匹配，文本流式处理 | O(n+m) 确定 | text 指针永不回溯，在线 |
| Trie | 多模式匹配，前缀查询 | O(m) 每次 | 空间大，自动补全绝配 |
KMP 用来自动机思路解决问题，比 Rabin-Karp 更可靠（无冲突）；Rabin-Karp 用来解决「多模式」时可以通过哈希预处理更优雅（比 KMP 逐个跑一遍快）；Trie 是另一条路——用空间换时间，适合前缀密集的场景。
通关挑战
- 搜索峰值元素：一个数组是单峰的（先升后降），在 O(log n) 时间内找到峰值索引（二分法的变体）
- KMP + Trie 混合：实现 AC 自动机（Aho-Corasick）——给一份文本和一组模式串，一次遍历找出所有模式串的所有出现位置（本质是 Trie + KMP 的失配指针）
- 最短回文串：给定一个字符串 s，通过在前面添加字符将其变成回文串，输出最短的结果。提示：KMP
- 二次哈希 Rabin-Karp：用两个不同模数同时计算哈希，把冲突概率降到几乎为零
- Trie 的 delete 操作：实现
trie.delete(word)，注意删除后清理冗余节点
验收标准
- [ ] 能一口气写对二分搜索的三种变体（存在、左边界、右边界）
- [ ] 能解释为什么旋转数组的二分要判断
arr[left] <= arr[mid] - [ ] 能手工推导任意模式串（如 "AAABAAA"）的 PMT 表
- [ ] 能口述 Rabin-Karp 的滚动哈希公式
- [ ] 能实现 Trie 树并分析空间开销
常见卡点
| 卡点 | 破解 |
|---|---|
二分的 mid 计算忘记防溢出 | 养成习惯：mid = left + (right - left) // 2 |
| 左边界右边界分不清 | 记住公式：找左边界（第一个≥target）用 right = len(arr) + while left < right；找右边界（最后一个≤target）也是这套模板，返回 left - 1 |
旋转数组的 arr[left] == arr[mid] 场景 | 有重复元素就要做线性缩进，最坏 O(n) 无法避免 |
KMP 的 PMT 构建 while j > 0 循环 | 这是在回退 j：当前字符和 pattern[j] 不匹配时，尝试利用已匹配部分的最长前缀-后缀 |
| Trie 的自动补全递归太深 | 1000 层递归 Python 会爆栈。可以改用栈做迭代 DFS |
| Rabin-Karp 的模运算负数 | Python 的 % 对负数结果为正，Java/C++ 要手动 + mod 调整 |
现在不需要理解
- BM 算法（Boyer-Moore）—— 比 KMP 更快（在某些场景是 KMP 的 3-5 倍），但构建复杂。它用「坏字符规则」+「好后缀规则」让模式串大步跳跃。C 标准库
memmem()和 GNU grep 用的都是 BM 的变体。 - Suffix Array / Suffix Tree—— 文本索引的利器，O(n) 构建后能在 O(m) 时间内回答任意子串是否出现。但构建算法（DC3 / SA-IS）极其复杂。
- Z Algorithm—— 另一种线性时间字符串匹配，比 KMP 更直观，但知名度低。
旅人笔记
- 二分搜索是「三分钟学会，一辈子写不完美」的算法。80% 的边界 bug 出在区间开闭不一致。
- 旋转数组问题是二分搜索最漂亮的变体——它让你认识到「有序」是一个相对概念。
- KMP 是算法美学的一个巅峰：用一个只有 m 长度的 PMT 表，省掉了 text 指针所有不必要的回溯。看懂 KMP，你就懂了「预计算+利用历史信息」这个极其重要的思维范式。
- Trie 是「空间换时间」最彻底的执行者。不要因为它吃内存就轻视它——在实际系统中（输入法、搜索引擎、拼写检查），Trie 的变体无处不在。
- 字符串匹配的世界里没有银弹。暴力的 O(n×m) 在短串场景反而是最优的（Java 的选择），工程选型永远要考虑数据分布。
一句话记住本章：「二分划区间，KMP建表不回头，Trie 通用前缀秀。」
→ 下一站预告
第 12 章我们将跳出「搜索」这个具体的意图，进入更高层次的算法设计范式：分治与回溯。
- 分治：三步走——分（Divide）、治（Conquer）、合（Combine）。最大子数组、逆序对。
- 回溯：做选择 → 递归 → 撤销。N 皇后、全排列、子集、子集和。
- 这两个范式是你进入动态规划之前的最后两把钥匙。
准备好了吗？思维的疆域要再次扩张了。