考频地图
本章几乎只考 KMP:求 next / nextval 数组、KMP 匹配时的比较次数或某次失配后的 j 值。手算 next 有固定方法,练 5 个模式串就熟了。
| 考点 | 考频 | 常见问法 |
|---|---|---|
| 串的存储 | ★☆☆☆☆ | “串的块链存储” |
| 朴素匹配 | ★★☆☆☆ | “最坏比较次数” |
| next / nextval | ★★★★★ | “模式串的 next 数组是” |
| KMP 匹配过程 | ★★★★☆ | “第二趟匹配从哪里开始”“共比较几次” |
串的存储与朴素匹配
串是内容受限的线性表(元素是字符)。存储方式:定长顺序存储(字符数组,超长截断)、堆分配存储(动态申请)、块链存储(每个结点存多个字符,存储密度 = 串值所占空间 ÷ 结点总空间)。
朴素(暴力)模式匹配
从主串每个位置开始,与模式串逐个比较;一旦失配,主串指针回退到本趟起点的下一个位置,模式串回到开头。
KMP 与 next 数组
一、KMP 的核心想法
二、手算 next 数组(下标从 1 开始)
- next[1] = 0,next[2] = 1(固定)。
- 对 j ≥ 3:看 P 的前 j − 1 个字符,找最长的“既是前缀又是后缀”的子串(不能是整串本身),长度为 k。
- next[j] = k + 1。
三、nextval:避免无效比较
若 P[j] == P[next[j]],那么在 j 处失配后跳到 next[j],比的还是同一个字符,必然再失配。于是继续往前跳:
四、复杂度
求 next 数组 O(m),匹配 O(n),总 O(m + n)。KMP 的优势在主串中存在很多“部分匹配”时才明显;一般情况下朴素算法实际也接近 O(n + m)。
- 题目若约定下标从 0 开始,next[0] = −1,整体比 1 起的版本小 1。看清约定再作答。
- 求 next[j] 看的是前 j − 1 个字符,不包括 P[j] 本身。
- 最长相等前后缀不能是整个子串自身。
- KMP 中主串指针 i 永不回退,这是它与朴素算法的根本区别。
真题与自测
一、真题问法
问法 1(2015 真题改写):“已知字符串 S 为 abaabaabacacaabaabcc,模式串 t 为 abaabc,采用 KMP 算法匹配,第一次出现失配(s[i] ≠ t[j])时 i = j = 5,则下次开始匹配时 i 和 j 的值分别是?”→ 下标从 0 起时 next[5] = 2,所以 i = 5、j = 2。
问法 2(2019 真题改写):“设主串 T = abaabaabcabaabc,模式串 S = abaabc,采用 KMP 算法,到匹配成功为止,单个字符的比较次数是?”→ 在上面的模拟器里输入可得 10 次。
二、折叠自测
1. 模式串 ababaa 的 next 数组(下标从 1 开始)?
0 1 1 2 3 4。
2. 上题的 nextval?
0 1 0 1 0 4。
3. 朴素匹配最坏时间复杂度?KMP 呢?
朴素 O(nm);KMP O(n + m)。
4. KMP 失配时主串指针怎么移动?
不动;只把模式串指针 j 改为 next[j](若为 0,则 i、j 同时后移)。
三、考前速览
next[j] = 前 j−1 位最长相等前后缀 + 1。
P[j] == P[next[j]] 时 nextval 继续向前取。
KMP 主串指针不回退,O(n + m)。
① 看清下标从 0 还是 1 开始。
② 前缀后缀不能取整串。
③ next 只与模式串有关,与主串无关。