字符串匹配：从暴力到 KMP

第三十章：字符串匹配 — 从暴力到 KMP

"在一段文本中找到一个模式串"——这个看似简单的问题，催生了计算机科学中最精巧的算法之一。从朴素的逐字符比对，到 KMP 算法一次性扫描文本不回退，背后是对失配信息的深刻利用。

字符串匹配是编辑器的 Ctrl+F、grep 命令、DNA 序列比对、入侵检测系统的核心操作。理解这些算法不仅是面试必备，更是理解"如何从问题结构中提取可复用信息"这一算法设计哲学的绝佳案例。

Level 1 · 你需要知道的

30.1 暴力匹配（Brute Force）

问题定义

给定文本串 text（长度 n）和模式串 pattern（长度 m），找到 pattern 在 text 中所有出现的位置。

暴力思路

尝试 text 中的每一个起始位置 i（从 0 到 n-m），逐字符比较 text[i..i+m-1] 与 pattern[0..m-1]。

def brute_force_search(text: str, pattern: str) -> list[int]:
    """暴力字符串匹配，返回所有匹配位置"""
    n, m = len(text), len(pattern)
    if m == 0:
        return list(range(n + 1))
    
    positions = []
    for i in range(n - m + 1):
        match = True
        for j in range(m):
            if text[i + j] != pattern[j]:
                match = False
                break
        if match:
            positions.append(i)
    return positions

时间复杂度：最坏 O(n * m)。例如 text = "aaaa...a"（n 个 a），pattern = "aaa...ab"（m-1 个 a + b），每个位置都要比较 m 次才发现不匹配。

为什么暴力不够好？ 考虑在一个 1GB 的日志文件中搜索一个 100 字符的关键词。n = 10^9，m = 100，暴力最坏需要 10^11 次比较。我们需要 O(n) 的算法。

30.2 KMP 算法的核心直觉

KMP 的关键观察

当暴力匹配在 text[i+j] != pattern[j] 处失败时，暴力做法是把起始位置右移一格（i → i+1），从头开始比较。但我们已经知道 text[i..i+j-1] == pattern[0..j-1]——这些已匹配的字符包含有价值的信息！

KMP 的核心问题是：匹配失败时，模式串能向右滑动多远而不错过任何可能的匹配？

答案取决于 pattern[0..j-1] 这段已匹配前缀中，最长的"既是前缀又是后缀"的真子串长度。这就是 next 数组（也叫 failure function 或 prefix function）。

直觉示例

text:    a b a b a c
pattern: a b a b a d
                  ↑ 失配在位置 5（pattern[5]='d' != text[5]='c'）

已匹配部分：pattern[0..4] = "ababa"
"ababa" 的最长真前缀 == 真后缀："aba"（长度 3）

这意味着：text 中匹配到的最后 3 个字符 "aba" 同时也是 pattern 的前缀
因此可以直接从 pattern[3] 继续比较，不需要回退 text 指针！

30.3 next 数组的构建

定义

next[j]（也记作 pi[j] 或 lps[j]）表示 pattern[0..j] 的最长真前缀（proper prefix），使得该前缀同时也是 pattern[0..j] 的后缀。

例如：

• pattern = "abab": next = [-1, 0, 0, 1, 2]（这里用 -1 做哨兵）
• 或者 lps = [0, 0, 1, 2]（不带哨兵）

构建算法

构建 next 数组本身就是一个"用 pattern 匹配自身"的过程：

def build_next(pattern: str) -> list[int]:
    """
    构建 KMP 的 next 数组（前缀函数）
    next[i] = pattern[0..i-1] 的最长真前缀后缀长度
    """
    m = len(pattern)
    next_arr = [0] * m  # next_arr[0] = 0，单个字符无真前缀
    
    j = 0  # 已匹配的前缀长度
    for i in range(1, m):
        # 失配时回退
        while j > 0 and pattern[i] != pattern[j]:
            j = next_arr[j - 1]
        
        # 匹配成功
        if pattern[i] == pattern[j]:
            j += 1
        
        next_arr[i] = j
    
    return next_arr

逐步演示（pattern = "ababac"）

i=0: next[0] = 0（定义）
i=1: pattern[1]='b', pattern[0]='a', 不等 → next[1] = 0
i=2: pattern[2]='a', pattern[0]='a', 相等 → j=1, next[2] = 1
i=3: pattern[3]='b', pattern[1]='b', 相等 → j=2, next[3] = 2
i=4: pattern[4]='a', pattern[2]='a', 相等 → j=3, next[4] = 3
i=5: pattern[5]='c', pattern[3]='b', 不等
     j = next[2] = 1
     pattern[5]='c', pattern[1]='b', 不等
     j = next[0] = 0
     pattern[5]='c', pattern[0]='a', 不等
     next[5] = 0

结果: next = [0, 0, 1, 2, 3, 0]

时间复杂度：O(m)。虽然有 while 循环，但 j 的总增量不超过 m，总减量也不超过 m。

30.4 KMP 完整匹配过程

def kmp_search(text: str, pattern: str) -> list[int]:
    """
    KMP 字符串匹配
    返回 pattern 在 text 中所有出现的起始位置
    """
    if not pattern:
        return list(range(len(text) + 1))
    
    n, m = len(text), len(pattern)
    next_arr = build_next(pattern)
    
    positions = []
    j = 0  # pattern 中已匹配的长度
    
    for i in range(n):
        # 失配时利用 next 数组回退 pattern 指针
        while j > 0 and text[i] != pattern[j]:
            j = next_arr[j - 1]
        
        # 当前字符匹配
        if text[i] == pattern[j]:
            j += 1
        
        # 完整匹配
        if j == m:
            positions.append(i - m + 1)
            j = next_arr[j - 1]  # 继续寻找下一个匹配
    
    return positions

完整匹配演示（text = "ababababac", pattern = "ababac"）

next = [0, 0, 1, 2, 3, 0]

i=0: text[0]='a', pattern[0]='a' → j=1
i=1: text[1]='b', pattern[1]='b' → j=2
i=2: text[2]='a', pattern[2]='a' → j=3
i=3: text[3]='b', pattern[3]='b' → j=4
i=4: text[4]='a', pattern[4]='a' → j=5
i=5: text[5]='b', pattern[5]='c' → 失配！
     j = next[4] = 3
     text[5]='b', pattern[3]='b' → j=4
i=6: text[6]='a', pattern[4]='a' → j=5
i=7: text[7]='b', pattern[5]='c' → 失配！
     j = next[4] = 3
     text[7]='b', pattern[3]='b' → j=4
i=8: text[8]='a', pattern[4]='a' → j=5
i=9: text[9]='c', pattern[5]='c' → j=6 = m → 匹配成功！
     位置 = 9 - 6 + 1 = 4
     j = next[5] = 0

结果: [4]（pattern "ababac" 出现在 text 的位置 4）

KMP 的核心性质

1. text 指针 i 永不回退：i 严格递增，每次循环 i 增加 1
2. 时间复杂度 O(n+m)：预处理 O(m)，匹配 O(n)
3. 在线算法：text 可以流式输入，每读入一个字符就能判断是否匹配

常见错误

1. next 数组下标偏移：有些实现用 next[0] = -1 作为哨兵，有些用 lps[0] = 0。面试时先说清楚自己的定义。
2. 匹配成功后忘记回退：找到一个匹配后，j 应该设为 next[j-1]（或对应的回退值），而不是 0——否则会错过重叠的匹配。
3. 空模式串：pattern 为空时的行为需要明确定义。

Level 2 · 它是怎么运行的

30.5 Boyer-Moore 算法

Boyer-Moore（1977）是实践中最快的单模式匹配算法。它的核心思想：从右向左比较，利用失配信息实现大幅跳跃。

坏字符规则（Bad Character Rule）

当 pattern[j] 与 text[i+j] 失配时，看 text[i+j] 这个"坏字符"在 pattern 中最右出现的位置 k：

• 如果 k < j：把 pattern 右移 j - k 位，让 pattern[k] 对齐坏字符
• 如果 k > j 或坏字符不在 pattern 中：把 pattern 右移到坏字符的下一位

def build_bad_char_table(pattern: str) -> dict[str, int]:
    """坏字符表：记录每个字符在 pattern 中最右出现的位置"""
    table = {}
    for i, ch in enumerate(pattern):
        table[ch] = i
    return table

好后缀规则（Good Suffix Rule）

当比较到 pattern[j] 失配时，已匹配的后缀是 pattern[j+1..m-1]（好后缀）。查找这个好后缀在 pattern 中其他位置的出现：

• 如果好后缀在 pattern 中别处出现（且前一个字符不同），对齐那个位置
• 如果好后缀的某个后缀是 pattern 的前缀，对齐那个前缀

好后缀规则的预处理较复杂，但它保证了最坏 O(n) 的匹配复杂度。

Boyer-Moore 简化实现（仅坏字符规则）

def boyer_moore_search(text: str, pattern: str) -> list[int]:
    """Boyer-Moore 匹配（简化版：仅坏字符规则）"""
    n, m = len(text), len(pattern)
    if m == 0:
        return list(range(n + 1))
    
    # 预处理坏字符表
    bad_char = build_bad_char_table(pattern)
    
    positions = []
    i = 0  # text 中当前对齐位置
    
    while i <= n - m:
        j = m - 1  # 从右向左比较
        
        while j >= 0 and pattern[j] == text[i + j]:
            j -= 1
        
        if j < 0:
            # 完全匹配
            positions.append(i)
            i += 1  # 简化处理，实际可以跳更多
        else:
            # 失配，使用坏字符规则
            bad_char_pos = bad_char.get(text[i + j], -1)
            shift = max(1, j - bad_char_pos)
            i += shift
    
    return positions

Boyer-Moore 的平均性能

在自然语言文本中，Boyer-Moore 的平均比较次数约为 n/m——比文本长度还小！原因是字母表较大时，坏字符规则经常能跳过整个 pattern 长度。这就是为什么 grep 命令默认使用 Boyer-Moore 变体。

Boyer-Moore vs KMP 的选择

30.6 Rabin-Karp 算法（滚动哈希）

核心思想

与其逐字符比较，不如用哈希值进行快速判断：如果 text[i..i+m-1] 的哈希值不等于 pattern 的哈希值，一定不匹配；如果相等，再逐字符验证（处理哈希冲突）。

关键技巧是滚动哈希（Rolling Hash）：从 text[i..i+m-1] 的哈希值可以 O(1) 计算 text[i+1..i+m] 的哈希值。

多项式哈希

把字符串看作一个 b 进制数（b 通常取 31 或 131），对大质数 p 取模：

$$h(s) = s[0] \cdot b^{m-1} + s[1] \cdot b^{m-2} + ... + s[m-1] \cdot b^0 \mod p$$

滚动更新： $$h(s[i+1..i+m]) = (h(s[i..i+m-1]) - s[i] \cdot b^{m-1}) \cdot b + s[i+m] \mod p$$

完整实现

def rabin_karp_search(text: str, pattern: str) -> list[int]:
    """Rabin-Karp 字符串匹配"""
    n, m = len(text), len(pattern)
    if m == 0:
        return list(range(n + 1))
    if m > n:
        return []
    
    # 哈希参数
    base = 131
    mod = 10**9 + 7
    
    # 计算 base^(m-1) mod p
    power = pow(base, m - 1, mod)
    
    # 计算 pattern 的哈希值
    pattern_hash = 0
    for ch in pattern:
        pattern_hash = (pattern_hash * base + ord(ch)) % mod
    
    # 计算 text 前 m 个字符的哈希值
    text_hash = 0
    for i in range(m):
        text_hash = (text_hash * base + ord(text[i])) % mod
    
    positions = []
    
    for i in range(n - m + 1):
        # 哈希值相等时验证
        if text_hash == pattern_hash:
            if text[i:i + m] == pattern:
                positions.append(i)
        
        # 滚动更新哈希值
        if i < n - m:
            text_hash = (text_hash - ord(text[i]) * power) % mod
            text_hash = (text_hash * base + ord(text[i + m])) % mod
            text_hash = (text_hash + mod) % mod  # 确保非负
    
    return positions

时间复杂度：

• 期望 O(n + m)：如果哈希函数选择得当，冲突很少
• 最坏 O(n * m)：所有位置都哈希冲突（极不可能）

Rabin-Karp 的独特优势

1. 多模式匹配：可以同时维护多个 pattern 的哈希值，一次扫描匹配多个模式
2. 二维模式匹配：可以推广到在矩阵中搜索子矩阵
3. 实现简单：代码比 KMP 和 Boyer-Moore 都短

哈希冲突的处理

单哈希的冲突概率约为 1/p。为了进一步降低误判：

• 使用双哈希（两组不同的 base 和 mod）
• 冲突概率降为 1/(p1 * p2) ≈ 10^-18，实际上不可能发生

30.7 Z 函数（Z-array）

定义

对于字符串 s，Z[i] 定义为 s 从位置 i 开始的子串与 s 的前缀的最长匹配长度。Z[0] 通常定义为 0 或 len(s)。

例如：s = "aabxaab"

Z[0] = 7（或 0，按约定）
Z[1] = 1  "a" 是 "aabxaab" 的前缀
Z[2] = 0  "b..." 不是前缀
Z[3] = 0  "x..." 不是前缀
Z[4] = 3  "aab" 是前缀
Z[5] = 1  "a" 是前缀
Z[6] = 0  "b" 不是前缀

O(n) 构建 Z 函数

def build_z_array(s: str) -> list[int]:
    """构建 Z 函数，O(n) 时间"""
    n = len(s)
    z = [0] * n
    z[0] = n  # 约定
    
    l, r = 0, 0  # [l, r) 是当前最靠右的匹配区间
    
    for i in range(1, n):
        if i < r:
            # i 在已知匹配区间内，可以利用已有信息
            z[i] = min(r - i, z[i - l])
        
        # 暴力扩展
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        
        # 更新最靠右的匹配区间
        if i + z[i] > r:
            l, r = i, i + z[i]
    
    return z

用 Z 函数做字符串匹配

构造字符串 pattern + "$" + text（$ 是不出现在两者中的分隔符），计算其 Z 数组。Z[i] == m 的位置 i（减去 m+1 的偏移）就是匹配位置。

def z_search(text: str, pattern: str) -> list[int]:
    """用 Z 函数进行字符串匹配"""
    m = len(pattern)
    combined = pattern + "$" + text
    z = build_z_array(combined)
    
    positions = []
    for i in range(m + 1, len(combined)):
        if z[i] == m:
            positions.append(i - m - 1)
    return positions

Z 函数 vs KMP 的 next 数组

两者本质上等价——Z 函数描述的是"从每个位置开始能匹配多长的前缀"，next 数组描述的是"每个前缀的最长真前缀后缀"。它们可以互相转化，但在不同问题中各有优势：

• Z 函数更直观：直接告诉你每个位置匹配前缀的长度
• next 数组更适合在线处理：流式输入时可以逐字符更新

Level 3 · 规范怎么定义的

30.8 KMP 的理论基础

Knuth, Morris, Pratt 1977 年论文

Donald Knuth、James Morris 和 Vaughan Pratt 在 1977 年发表 "Fast Pattern Matching in Strings"（SIAM Journal on Computing, Vol. 6, No. 2）。这篇论文证明了：

1. 定理 1：存在一种算法，在最坏情况下只需 n + m - 1 次字符比较即可完成匹配（不计 next 数组的构建）。

2. 定理 2：next 数组可以在最多 2m - 3 次比较中构建完成。

3. 推论：KMP 算法的总比较次数不超过 2n（匹配阶段）+ 2m（预处理阶段）= 2(n+m)。

KMP 与自动机的关系

KMP 算法实际上构造了一个确定有限自动机（DFA）的简化版本。完整 DFA 的转移表大小为 O(m * |Σ|)，而 KMP 只用 O(m) 的 next 数组就能模拟 DFA 的所有转移——通过失配时的链式回退。

Knuth 在论文中指出，KMP 可以看作是 Morris 和 Pratt 早期工作（1970 年的技术报告）的改进版，结合了 Knuth 对失配函数的数学分析。

最优性

1977 年的论文还证明了一个下界：任何正确的字符串匹配算法在最坏情况下至少需要 n + m - O(1) 次比较。KMP 的 n + m - 1 几乎紧密匹配这个下界。

30.9 Boyer-Moore 的理论

Boyer 和 Moore 1977 年论文

Robert Boyer 和 J Strother Moore 同年发表 "A Fast String Searching Algorithm"（Communications of the ACM, Vol. 20, No. 10）。

关键定理：

• 仅使用坏字符规则时，最坏复杂度为 O(n * m)
• 加入好后缀规则后，最坏复杂度降为 O(n + m)（由 Galil, 1979 年证明完整版）
• 在均匀分布的随机文本中，平均比较次数为 O(n/m)

子线性时间的直觉

为什么 Boyer-Moore 平均可以比 O(n) 更快？因为它不需要查看 text 的每个字符！当字母表足够大时（如 ASCII 的 256 个字符），坏字符在 pattern 中不存在的概率很高，每次失配可以跳过整个 pattern 长度。

对于 m = 10、|Σ| = 256 的情况，一个随机字符不在 pattern 中的概率约为 (1 - 10/256) ≈ 0.96，意味着大部分位置可以一次跳 10 格。

30.10 字符串哈希的理论基础

多项式哈希的冲突概率

给定两个不同的长度为 m 的字符串 s1 和 s2，使用随机基数 b（从 [1, p-1] 中均匀选取）和质数模 p，它们哈希值相同的概率为：

$$\Pr[h(s1) = h(s2)] \leq \frac{m-1}{p}$$

这来自 Schwartz-Zippel 引理：一个最多 m-1 次的非零多项式在 Z_p 上最多有 m-1 个根。

实际参数选择

• p = 10^9 + 7：冲突概率约 m/10^9，对 m <= 10^5 足够安全
• p = 10^9 + 9：另一个常用质数
• 双哈希：(p1, p2) = (10^9+7, 10^9+9)，冲突概率约 10^-18

Carter-Wegman 通用哈希

J. Lawrence Carter 和 Mark Wegman 在 1979 年 "Universal Classes of Hash Functions"（Journal of Computer and System Sciences）中建立了通用哈希的理论框架。多项式哈希属于这个框架中的一类。

Karp 和 Rabin 1987 年论文

Richard Karp 和 Michael Rabin 的 "Efficient Randomized Pattern-Matching Algorithms"（IBM Journal of Research and Development, 1987）正式分析了滚动哈希用于字符串匹配的期望复杂度，证明了在适当选择哈希参数时，算法的期望运行时间为 O(n + m)。

30.11 前缀函数的数学性质

性质 1：前缀函数的值构成一个"链"

对于任意位置 j，序列 j, next[j-1], next[next[j-1]-1], ... 形成严格递减序列直到 0。这意味着从任何位置回退到 0 的跳数最多为 O(log m)... 不，实际上最坏是 O(m)，但总跳数是 O(m) 的——这就是摊还分析的精髓。

性质 2：摊还分析

KMP 匹配阶段 while 循环的总执行次数不超过 n。证明：

• j（匹配长度）每次外层循环最多增加 1
• j 的总增量不超过 n
• while 循环每次让 j 减小至少 1
• j 的总减量不超过 j 的总增量 ≤ n
• 因此 while 循环总执行次数 ≤ n

性质 3：周期性

如果 next[m-1] > 0 且 m % (m - next[m-1]) == 0，则 pattern 有长度为 m - next[m-1] 的周期。

例如：pattern = "abcabc"，next[5] = 3，周期 = 6 - 3 = 3，pattern 确实是 "abc" 重复两次。

这个性质在 LeetCode #459（重复子字符串）中直接使用。

Level 4 · 边界与陷阱

30.12 面试题详解：实现 strStr()（LeetCode #28）

问题

实现 strStr()：返回 pattern 在 text 中第一次出现的位置，不存在则返回 -1。

面试策略

1. 先写暴力：证明你理解问题，O(n*m) 的暴力只有 5-6 行
2. 如果面试官要求优化：实现 KMP，重点讲清楚 next 数组的含义
3. 如果时间充裕：讨论各算法的优缺点

def str_str(haystack: str, needle: str) -> int:
    """LeetCode 28: 实现 strStr()"""
    if not needle:
        return 0
    
    # KMP 实现
    m = len(needle)
    # 构建 next 数组
    next_arr = [0] * m
    j = 0
    for i in range(1, m):
        while j > 0 and needle[i] != needle[j]:
            j = next_arr[j - 1]
        if needle[i] == needle[j]:
            j += 1
        next_arr[i] = j
    
    # 匹配
    j = 0
    for i in range(len(haystack)):
        while j > 0 and haystack[i] != needle[j]:
            j = next_arr[j - 1]
        if haystack[i] == needle[j]:
            j += 1
        if j == m:
            return i - m + 1
    
    return -1

面试官常见追问：

• "next 数组的 while 循环为什么是 O(m)？"——摊还分析，j 的总增减不超过 2m
• "KMP 和 Boyer-Moore 什么时候选哪个？"——小字母表（DNA: ACGT）选 KMP，大字母表选 BM
• "如果文本是流式输入呢？"——KMP 天然支持，BM 不行（需要从右往左比较）

30.13 面试题详解：重复子字符串（LeetCode #459）

问题

判断字符串 s 是否可以由某个子串重复多次构成。例如 "abab" → True（"ab" 重复两次）。

方法 1：KMP 的 next 数组

def repeated_substring_pattern(s: str) -> bool:
    """利用 KMP next 数组判断重复子串"""
    n = len(s)
    next_arr = [0] * n
    j = 0
    for i in range(1, n):
        while j > 0 and s[i] != s[j]:
            j = next_arr[j - 1]
        if s[i] == s[j]:
            j += 1
        next_arr[i] = j
    
    # next[n-1] > 0 且 n 能被 (n - next[n-1]) 整除
    period = n - next_arr[n - 1]
    return next_arr[n - 1] > 0 and n % period == 0

为什么这样做？ 如果 s 有一个周期 p（s = t * k，|t| = p），那么 s[p:] == s[:n-p]，即 s 的前 n-p 个字符构成 s 的后缀。这意味着 next[n-1] >= n - p。而最长前缀后缀长度 next[n-1] 给出的周期 n - next[n-1] 恰好是最短周期。

方法 2：字符串拼接技巧

def repeated_substring_pattern_v2(s: str) -> bool:
    """字符串拼接法"""
    doubled = (s + s)[1:-1]  # 去掉首尾各一个字符
    return s in doubled

直觉：如果 s = "abab"，则 s+s = "abababab"，去掉首尾得 "bababa"。如果 s 是重复串，那么在 s+s（去首尾后）中一定还能找到 s；反之不能。

30.14 面试题详解：最短回文串（LeetCode #214）

问题

在字符串 s 前面添加尽可能少的字符，使其成为回文串。

分析

关键观察：需要找到 s 的最长回文前缀。设最长回文前缀长度为 k，则需要在前面加上 s[k:][::-1]。

KMP 解法

构造字符串 s + "#" + s[::-1]，计算其 next 数组。最后一位的 next 值就是 s 的最长回文前缀长度。

def shortest_palindrome(s: str) -> str:
    """LeetCode 214: 最短回文串"""
    if not s:
        return s
    
    # 构造 s + "#" + reverse(s)
    rev_s = s[::-1]
    combined = s + "#" + rev_s
    
    # 计算 next 数组
    n = len(combined)
    next_arr = [0] * n
    j = 0
    for i in range(1, n):
        while j > 0 and combined[i] != combined[j]:
            j = next_arr[j - 1]
        if combined[i] == combined[j]:
            j += 1
        next_arr[i] = j
    
    # next 数组最后一个值 = s 的最长回文前缀长度
    longest_palindrome_prefix = next_arr[-1]
    
    # 需要添加的部分
    suffix_to_add = rev_s[:len(s) - longest_palindrome_prefix]
    return suffix_to_add + s

为什么这样做？

构造 s + "#" + rev_s 后，next 数组最后一位的值 k 表示：combined 的最长前缀（= s 的前缀）使得它同时是 combined 的后缀（= rev_s 的后缀 = s 的前缀的逆序）。

"s 的前缀"等于"s 的前缀的逆序"——这正是回文的定义！所以 k 就是 s 的最长回文前缀长度。

示例：s = "aacecaaa"

• rev_s = "aaacecaa"
• combined = "aacecaaa#aaacecaa"
• next 数组最后一位 = 7（前缀 "aacecaa" 是回文）
• 需要加的 = rev_s[:8-7] = "a"
• 结果 = "a" + "aacecaaa" = "aaacecaaa"

30.15 字符串算法的工程实践

实际系统中的选择

Python 内置实现

Python 的 str.find() 和 in 操作符使用了修改版的 Boyer-Moore-Horspool 算法（CPython 实现在 Objects/stringlib/fastsearch.h）。对于短模式（< 6 字符），退化为暴力搜索因为预处理开销不值得。

面试中的建议

1. 默认先给暴力解——简洁正确
2. 如果被要求优化，KMP 是最安全的选择（确定性 O(n+m)，代码量适中）
3. 提到 Boyer-Moore 作为实际更快的替代方案
4. Rabin-Karp 在需要多模式匹配或面试官提示"哈希"时使用

本章小结

1. 暴力匹配：O(n*m)，简单但面对大数据量不够快。

2. KMP 算法：O(n+m)，核心是 next 数组——记录模式串每个前缀的最长真前缀后缀，失配时不回退 text 指针。由 Knuth、Morris、Pratt（1977）提出。

3. Boyer-Moore：实践中最快，平均 O(n/m)。从右向左比较，利用坏字符规则和好后缀规则实现大步跳跃。

4. Rabin-Karp：滚动哈希实现 O(1) 的窗口滑动，期望 O(n+m)。优势在于多模式匹配和实现简单。

5. Z 函数：与 KMP 等价但有时更直观。Z[i] 直接给出从位置 i 开始能匹配多长的前缀。

6. 面试核心：掌握 KMP 的 next 数组构建和匹配过程，能手写代码，能解释摊还 O(n+m) 的证明。