返回：0300 数据结构总目录 · 上一章：0310 Chap10 优先级队列 · 下一章：0312 Chap12 排序

1、学习目标

串这一章的重点不是“会用字符串”，而是理解模式匹配为什么可以从朴素回溯优化到线性扫描。

模块 要掌握的内容
串 ADT 长度、子串、拼接、比较、查找
蛮力匹配 双指针、回退、最坏复杂度
KMP next 表、主串不回退、分摊线性
BM 坏字符、好后缀、从右向左匹配
Karp-Rabin 滚动哈希、指纹、冲突校验

2、资料范围

PDF 课件 内容
11.String.A.ADT.pdf 串的定义和 ADT
11.String.B1-B2.Brute_Force 蛮力匹配
11.String.C1-C6.KMP KMP、next 表、改进与分摊分析
11.String.D1-D4.BM_BC BM 坏字符策略
11.String.E1-E3.BM_GS BM 好后缀策略
11.String.F1-F2.Karp_Rabin Karp-Rabin 指纹匹配

3、串 ADT

字符串是字符序列：

1
S = s0 s1 s2 ... s(n-1)

常见操作：

操作 含义
length() 串长
substr(i, k) 从 i 开始取长度 k 的子串
concat(t) 拼接
compare(t) 字典序比较
find(p) 查找模式串 p

串匹配问题：

1
2
3
文本串 T，长度 n
模式串 P，长度 m
找出 P 在 T 中第一次出现的位置

4、蛮力匹配

朴素想法：从文本串每个位置开始，逐字符比较模式串。

1
2
3
4
5
6
7
8
9
int bruteForce(const string& T, const string& P) {
    int n = T.size(), m = P.size();
    for (int i = 0; i <= n - m; ++i) {
        int j = 0;
        while (j < m && T[i + j] == P[j]) ++j;
        if (j == m) return i;
    }
    return -1;
}

复杂度：

情况 复杂度
最好 O(m)
一般 依文本和模式而定
最坏 O(nm)

最坏情况例子：

1
2
T = aaaaaaaaaab
P = aaaab

每次都先匹配一串 a，最后才失败，重复比较很多。

5、KMP

KMP 的核心是：失配后不让主串指针回退，而是根据模式串自身结构移动模式串。

next[j] 表示当 P[j] 处失配时，模式串应该跳到哪个位置继续比较。

直觉：

1
已匹配部分中，寻找最长的“真前缀 = 真后缀”

例如：

1
2
P = abababca
前缀和后缀中重复出现 ab、abab

5.1 主算法

1
2
3
4
5
6
7
8
9
10
11
12
int kmp(const string& T, const string& P, const vector<int>& next) {
    int i = 0, j = 0;
    while (i < T.size() && j < P.size()) {
        if (j < 0 || T[i] == P[j]) {
            ++i;
            ++j;
        } else {
            j = next[j];
        }
    }
    return j == P.size() ? i - j : -1;
}

主串 i 只前进不后退，这是 KMP 能做到线性的关键。

5.2 构造 next

一种常见构造方式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> buildNext(const string& P) {
    vector<int> next(P.size());
    int j = 0;
    int t = next[0] = -1;
    while (j + 1 < P.size()) {
        if (t < 0 || P[j] == P[t]) {
            ++j;
            ++t;
            next[j] = t;
        } else {
            t = next[t];
        }
    }
    return next;
}

改进版 next 会在 P[j] == P[t] 时继续跳，避免失配后又立刻比较同样字符。

KMP 复杂度：

步骤 复杂度
构造 next O(m)
匹配 O(n)
总计 O(n+m)

6、BM 算法

BM 从模式串右端开始匹配，利用“坏字符”和“好后缀”两条经验移动模式串。它在自然语言文本中通常很快。

6.1 坏字符

从右向左比较时，如果 T[i] != P[j]，则 T[i] 是坏字符。模式串可以移动到让模式串中最靠右的同字符对齐坏字符的位置。

若模式串中没有这个字符，可以整体跨过坏字符。

坏字符表记录：

1
bc[c] = 字符 c 在模式串中最靠右的位置

6.2 好后缀

如果后缀已经匹配成功，但前一位失配，则这段已匹配后缀是好后缀。移动时尽量让模式串中另一个相同后缀对齐它；如果不存在，就找好后缀的最长后缀与模式串前缀对齐。

BM 实际移动距离通常取两种策略的较大者：

1
shift = max(bad_character_shift, good_suffix_shift)

6.3 性能

算法 最坏 常见表现
蛮力 O(nm) 简单文本还行
KMP O(n+m) 稳定线性
BM 可优化到线性 实际常跳得很远

BM 适合模式串较长、字符集较大、文本较自然的情况。

7、Karp-Rabin

KR 把长度为 m 的子串映射成哈希值。匹配时先比较哈希，哈希相同再逐字符确认。

滚动哈希：

1
2
hash(T[i+1 ... i+m])
可由 hash(T[i ... i+m-1]) O(1) 更新

基本流程：

  1. 计算模式串哈希。
  2. 计算文本前 m 个字符哈希。
  3. 滑动窗口，每次更新哈希。
  4. 哈希相等时做字符校验，避免冲突误判。

KR 适合多模式、指纹过滤、需要快速排除大量不可能位置的场景。

8、算法对比

算法 预处理 匹配 优点 注意
蛮力 无 最坏 O(nm) 最简单 容易重复比较
KMP O(m) O(n) 主串不回退 next 表要理解
BM O(m+字符集) 实践很快 跳跃距离大 实现细节多
KR O(m) 期望 O(n) 哈希过滤 要处理冲突

9、易错点

易错点 修正
KMP 只背模板 要能解释 next 的前后缀含义
KMP 主串回退 主串指针不回退，回退的是模式串指针
BM 从左向右写 BM 的典型比较从右向左
KR 哈希相等就认为匹配 哈希相等后还要字符确认
忽略空模式串 实现时要定义清楚返回约定

10、复盘清单

检查项 状态
能手动模拟蛮力匹配失败过程 待复盘
能解释 KMP 为什么主串不回退 待复盘
能手算一个短模式串的 next 表 待复盘
能区分 BM 的坏字符和好后缀 待复盘
能说明 KR 为什么需要二次确认 待复盘