比较朴素匹配与 KMP,掌握主串和模式串的匹配过程、next 数组的构造与失配回退,并理解 nextval 的优化目的。
# 一、模式匹配问题
给定主串 和模式串 ,模式匹配要找出 在 中首次出现的位置。若 、,本文代码使用从 开始的数组下标;若模式串为空,约定返回 。
若目标是返回所有匹配位置,而不是首次位置,成功后还需继续扫描;KMP 可令模式指针回退到匹配后缀对应的最长前后缀位置,再继续搜索。
# 二、朴素模式匹配
朴素算法依次尝试每个可能的起始位置。字符相同则继续比较;一旦失配,就将模式串右移一位,从新的起点重新比较。
1 | int NaiveIndex(const char text[], int n, const char pattern[], int m) { |
设主串长度为 ,模式串长度为 。最坏情况下,每个起始位置都比较接近 个字符,因此时间复杂度为 ,常简写为 ;额外空间为 。
# 三、KMP 的核心思想
KMP(Knuth-Morris-Pratt)在失配时利用模式串自身的重复结构,避免把主串指针退回到刚才比较过的位置。已经匹配的模式串前缀中,若某个后缀也是前缀,就可以把模式串移到这个相同前后缀继续比较。
真前缀不等于整个串,真后缀也不等于整个串。对于串 P [0..j-1],其最长相等真前缀与真后缀的长度,就是失配后能够保留的已匹配字符数。
本文采用带哨兵的零基 next 约定:
- next[0] = -1;
- 对 j > 0,next [j] 表示在模式串下标 j 处失配后,模式串下一次应比较的下标;
- 若主串当前字符与模式串下标 j 失配,就令 j = next [j];主串下标不回退。
有些教材把 next 定义成最长相等真前后缀的长度,或使用从 开始的下标。它们表示同一回退信息,但数组的首项、表中数值和代码不能混用。
# 四、构造 next 数组
设模式串为 ababaca,其字符下标从 开始。每一位失配时的回退位置如下。
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 字符 | a | b | a | b | a | c | a |
| next[j] | -1 | 0 | 0 | 1 | 2 | 3 | 0 |
例如在下标 的字符 c 处失配,前面已匹配的 ababa 有最长相等真前后缀 aba,长度为 ,因此令模式下标回到 ,而不是回到 。
1 | void BuildNext(const char pattern[], int m, int next[]) { |
next 数组至少需要 个单元,因为构造过程会写入 next [m]。匹配过程中只在 时访问模式串字符。
# 五、KMP 匹配过程
1 | int KMPIndex(const char text[], int n, const char pattern[], int m, |
以主串 ababababaca、模式串 ababaca 为例:
- 前五个字符 ababa 匹配,主串下标为 、模式下标为 。
- 主串字符 b 与模式字符 c 失配,令 ,主串下标保持为 。
- 此时主串和模式下标 都是字符 b,继续前进,不必重比前缀 aba。
- 后续再次失配时仍按 next 回退,最终从主串下标 找到模式串。
若 ,表示已没有可保留的模式前缀,主串指针和模式指针同时向后移动一位。若 ,说明完整模式串匹配成功,起始下标为 。
构造 next 和执行匹配都为线性扫描,时间复杂度为 ,辅助空间为 。
# 六、nextval 的改进
普通 next 有时会回退到一个与刚刚失配字符相同的模式字符,造成可预知的重复比较。修正后的 next 常记作 nextval:若 P [j] 与 P [next [j]] 相同,就继续采用 nextval [next [j]];否则仍采用 next [j]。
对模式串 ababaa,按上述零基约定:
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 字符 | a | b | a | b | a | a |
| next[j] | -1 | 0 | 0 | 1 | 2 | 3 |
| nextval[j] | -1 | 0 | -1 | 0 | -1 | 3 |
例如 j=4 时字符 a 失配,next [4]=2,而 P [4]=P [2]=a,继续比较仍会立即失配,因此修正为 nextval [2]=-1。nextval 只减少一些重复比较,不改变匹配结果;掌握 next 的含义和构造通常更重要。
计算 next 时,要先确认失配发生在模式串的哪一个下标、数组记录的是前后缀长度还是下一比较位置。只有在定义、下标和匹配代码完全一致时,表格才可直接使用。
# 七、考场检查清单
- 朴素算法在每次失配后把起点右移一位,最坏复杂度为 。
- KMP 失配时主串指针不回退,只调整模式串下标。
- next 保存的是失配后的回退信息;不同教材可能采用不同下标约定。
- 最长相等真前后缀不包含整个已匹配串本身。
- nextval 避免跳到一个会与当前失配字符重复比较的位置。
