数据结构与算法 · 第 4 讲：串与 KMP 模式匹配
本页目录
数据结构与算法 第四讲：字符串与 KMP
来源：第四章 String 课件（66 页）、配套 Markdown、KMP 比较次数模拟和 MOOC 第四章习题。
1. 串、编码与存储
串是字符的有限序列，空串长度为 0，空白串含空格且长度非零。子串必须连续，子序列只要求保持相对次序。课件将非空且不等于原串的子串称为真子串。
ASCII 使用 7 位编码，数字、大写字母、小写字母分别连续。Unicode 给字符分配码点，UTF-8 以 1 至 4 字节编码码点。C++ char 是字节，std::string::size() 计编码单元；字节数、码点数与显示宽度分别是不同的量。
字典序看首个不同元素；若一串是另一串前缀，则较短者小。因此字符串 "123" < "1234" < "23"。字符串字面量之间直接用 < 会比较指针，比较内容应使用字符串对象或比较函数。
C 风格串以 \0 结束，char s[M] 最多容纳 字节内容。局部数组 char s[6]; 没有初始化，不能把它当作空串；char s[6] = {}; 才将首字节置零。
2. String 类与变长管理
类保存缓冲区指针与长度，分配空间同时容纳终止符。构造分配，析构释放；拷贝构造和拷贝赋值复制字符本体，形成独立所有权。只复制指针会导致共享修改和重复释放。
赋值顺序是申请新空间、复制、释放旧空间、接管新指针。移动操作转移缓冲区的所有权。修改器返回 String& 可支持连续追加。
append 拼接，substr(start,count) 取连续区间，find 找首个位置，compare 返回大小关系。课件教学版每次按新长度重分配，追加一个字符为 ；按倍数扩容的实现才能使连续追加达到摊还 。
strlen 扫描到终止符，strcmp 按字典序比较，strchr/strrchr 分别定位首次和末次出现。数组赋值不等于复制内容。
3. 朴素模式匹配
主串 长 ，模式 长 ，均从下标 0 开始。令 为主串下标， 为模式下标：相等则同时加 1；失配则主串回到本趟起点后一位，模式回到 0。
匹配成功时主串下标已经越过匹配段，起点为 。课件指出原书返回式多加了 1。
最多检查 个起点，每趟至多 次比较，最坏 ；反例取主串全部为 a、模式为若干 a 后接 b。
4. 普通 next、nextval 与前缀函数
本文统一记号：next[0]=-1，next[j] 是 的最长相等真前后缀长度。前缀函数 pi[j] 则针对 ，所以普通 next[j]=pi[j-1]。
失配时将 改为 next[j]，主串下标不动。已经匹配的后缀重新对齐模式的同长前缀。 若 P[j]==P[next[j]]，退到该位置还会与同一主串字符失配，可以继续沿失败链跳过，得到 nextval。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
P[j] | B | A | A | A | B | B | B | A | A |
pi[j] | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 2 | 3 |
next[j] | −1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 2 |
nextval[j] | −1 | 0 | 0 | 0 | −1 | 1 | 1 | 0 | 0 |
4.1. KMP 的匹配循环
i = 0; j = 0
while i < n and j < m:
if j == -1 or T[i] == P[j]:
i += 1; j += 1
else:
j = nextval[j]成功条件为 ，返回 ；空模式匹配在位置 0。j==-1 是移动指针的分支，不执行字符比较，统计比较次数时不计入。
主串下标至多前进 次。模式下标的每次增加伴随主串前进，所有回退的总量受增加总量限制，所以匹配 ；预处理 ，总时间 ，额外空间 。
4.2. 比较次数例题
模式 BAAABBBAA，主串 BAAABBBCDDDCCHHHHBBBAAABBBAADD。用 nextval 在主串下标 19 首次成功，共 31 次比较：最初连续成功 7 次，C 处比较 2 次，下标 8 至 16 比较 9 次，下标 17 至 19 比较 5 次，最后 8 次成功。普通 next 在 C 处多比较一次，共 32 次。
5. 最小周期与整串重复
令整串最长真边界长度为 ，则最小周期 。边界条件 与周期定义是同一组等式。
abcabcabc：，是 abc 的三次重复。 ababa：，周期 2 不整除长度 5，不能整串重复。 abcd：，没有更短重复单元。
非空串由更短串重复至少两次，当且仅当 且 被 整除。优化 nextval 跳过了部分边界，不能替代前缀函数求周期。
循环移位判定：两串等长，且第一串出现在第二串与自身连接的串中。连接可交换 时，非空的 是某一公共串的整数次重复。
6. 习题方法
- 不同子串： 计的是按起止位置区分的非空子串，按内容去重后可能更少；字符互异时再加空串得到 。
- 互补回文：依次比较首尾对应字符是否互补，再向中间推进。
- 串表达式：逐层写出长度、索引、子串、替换、连接的中间值，统一下标起点。
- 行编辑器：行结构管理插入删除，KMP 负责行内匹配；两种操作分别维护各自状态。