2025/11/8约 923 字大约 3 分钟
数据结构KMP算法的两个数组
最近很忙, 随缘更新.
数据结构完全是一门理论的, 抽象的, 而且完全脱离实际的一门课程((, 因此本节内容放在了学习而非开发分类下.
今天学习KMP算法彻底被气到了(甚至上课时候直接把书撕了), 数据结构这门课程玷污了优雅且伟大的KMP算法.
所以内容完全没想去理解, 本节主要分享下next和nextval数组的求法, 仅提供方法, 无任何原理讲解.
next数组
next数组为对应位置前面构成的串的最长相等前后缀的长度 + 1, 此外, 定义 next[1] = 0, next[2] = 1.(注意本数据结构的教材数组索引从1开始)
以 abcaabbabcab 为例, 解释各个名词如下:
- 对应位置前构成的串: 对于位置5(b), 前面构成的串为
abca - 前缀: 指的是以第一个元素开始, 不同长度的真子串. 如
abca前缀有a,ab,abc - 后缀: 指的是以最后一个元素结尾, 不同长度的真子串. 如
abca后缀有a,ca,bca - 相等前后缀: 指的是前缀和后缀中相等的部分. 如
abca的相等前后缀有a - 最长相等前后缀: 指的是相等前后缀中最长的部分. 如
abca的最长相等前后缀为a, 长度为1
因此, next[5] = 1 + 1 = 2
下表为 abcaabbabcab 的 next 数组:
| 位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| pat | a | b | c | a | a | b | b | a | b | c | a | b |
| next | 0 | 1 | 1 | 1 | 2 | 2 | 3 | 1 | 2 | 3 | 4 | 5 |
如何快速确定各个值, 对于这样一长串, 我们直接肉眼搜寻它前面这样一串最长的相同一个部分, 如下:
nextval数组
首先我们得到 next 数组, 然后列出表格如下:
| j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| pat[j] | a | b | c | a | a | b | b | a | b | c | a | b |
| next[j] | 0 | 1 | 1 | 1 | 2 | 2 | 3 | 1 | 2 | 3 | 4 | 5 |
| pat[next[j]] | NULL | a | a | a | b | b | c | a | b | c | a | a |
注意第四行是以 next[j] 为索引, 求 pat 对应位置的值.
之后比较 pat[j] 和 pat[next[j]] 并记录.
| j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| pat[j] | a | b | c | a | a | b | b | a | b | c | a | b |
| next[j] | 0 | 1 | 1 | 1 | 2 | 2 | 3 | 1 | 2 | 3 | 4 | 5 |
| pat[next[j]] | NULL | a | a | a | b | b | c | a | b | c | a | a |
| == | NULL | F | F | T | T | T | F | T | T | T | T | T |
初始化nextval[1] = 0.
对于所有 F 项, nextval[j] = next[j], 直接抄下来即可; 对于所有 T 项, nextval[j] = nextval[next[j]], 即取 next[j] 位置 nextval 的值, 多套一层.
| j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| pat[j] | a | b | c | a | a | b | b | a | b | c | a | b |
| next[j] | 0 | 1 | 1 | 1 | 2 | 2 | 3 | 1 | 2 | 3 | 4 | 5 |
| pat[next[j]] | NULL | a | a | a | b | b | c | a | b | c | a | a |
| == | NULL | F | F | T | T | T | F | T | T | T | T | T |
| nextval[j] | 0 | 1 | 1 | 0 | 1 | 1 | 3 | 0 | 1 | 1 | 0 | 1 |
完全不理解它们的作用, 死记硬背好了.
本文章仅负责北大出版社C语言数据结构和湖南大学的数据结构课程.