考研全科复习

Appearance

408 ​

数据结构 ​

字符串模式匹配（BF/KMP） ​

定位信息

项目内容
章节第六章 查找 · 6.8
知识单元编号DS-06-08
核心概念BF 算法（暴力匹配）、KMP 算法、next 数组、nextval 数组
前置知识字符串基本操作
考试权重★★★★★（极高频，综合题必考 KMP 的 next/nextval 数组计算）

知识点讲解

一、模式匹配的基本概念

模式匹配（Pattern Matching）： 在主串 S 中查找模式串 T 的第一次出现位置。S 长度为 n，T 长度为 m。

目标： 返回 T 在 S 中首次出现的起始下标（或 0 表示匹配失败）。

二、BF 算法（Brute-Force，朴素匹配）

基本思想： 从主串 S 的每个位置开始，逐字符与模式串 T 比较。若某位不匹配，S 回退到上次开始位置的下一个，T 回退到开头。

时间复杂度： 最坏 O(n × m)，平均 O(n + m)。

BF 算法伪代码（C 风格）：

c
// BF 模式匹配：在主串 S[1..n] 中查找模式串 T[1..m]
// 返回匹配成功的起始位置，失败返回 0
int BF(char S[], int n, char T[], int m) {
    int i = 1;  // 主串指针
    int j = 1;  // 模式串指针
    while (i <= n && j <= m) {
        if (S[i] == T[j]) {
            i++;    // 匹配成功，继续比较下一位
            j++;
        } else {
            i = i - j + 2;  // 主串指针回退到上次开始的下一位
            j = 1;           // 模式串指针回退到开头
        }
    }
    if (j > m)
        return i - m;  // 匹配成功，返回起始位置
    else
        return 0;      // 匹配失败
}

BF 的核心问题： 每次失配时，主串指针 i 回退，导致大量重复比较。KMP 算法通过分析模式串的结构，避免了 i 的回退。

三、KMP 算法（Knuth-Morris-Pratt）

核心思想： 利用已匹配的信息，当失配发生时，主串指针 i 不回退，只将模式串指针 j 移动到一个合适的位置（由 next 数组决定）。

关键概念——前缀、后缀、最长公共前后缀：

  • 前缀： 字符串的所有以第一个字符开头的子串（不含自身）；
  • 后缀： 字符串的所有以最后一个字符结尾的子串（不含自身）；
  • 最长公共前后缀（LPS）： 前缀和后缀中最长的相同子串的长度。

next 数组的定义：

next[j] 的含义：当 T[j] 与 S[i] 失配时，j 应移动到 next[j] 位置继续比较。

next[j] 的值 = T[1..j-1] 的最长公共前后缀长度 + 1

j1234567
T[j]abaabca
next[j]0112231
  • next[1] = 0（特殊规定，失配时 i 前进，j 回到 0）
  • next[2] = 1（"a" 的最长公共前后缀长度 = 0，+1 = 1）
  • next[3] = 1（"ab" 无公共前后缀，长度 = 0，+1 = 1）
  • next[4] = 2（"aba" 的最长公共前后缀 = "a"，长度 = 1，+1 = 2）
  • ...

KMP 算法伪代码（C 风格）：

c
// KMP 模式匹配
// next[] 数组已预先计算好
int KMP(char S[], int n, char T[], int m, int next[]) {
    int i = 1;  // 主串指针（不回退！）
    int j = 1;  // 模式串指针
    while (i <= n && j <= m) {
        if (j == 0 || S[i] == T[j]) {
            i++;
            j++;    // 匹配成功或 j=0 时，两指针均前进
        } else {
            j = next[j];  // 失配：i 不动，j 跳转到 next[j]
        }
    }
    if (j > m)
        return i - m;  // 匹配成功
    else
        return 0;      // 匹配失败
}

四、next 数组的求法（手动计算步骤）

对模式串 T[1..m]，逐位计算 next[j]：

  1. next[1] = 0（固定值）
  2. next[2] = 1（固定值）
  3. 对于 j ≥ 3：看 T[1..j-1] 的最长公共前后缀长度 len，next[j] = len + 1

手动求法口诀： "看前 j-1 个字符，最长相等前后缀，长度加 1。"

next 数组计算伪代码（C 风格）：

c
// 求模式串 T[1..m] 的 next 数组
void GetNext(char T[], int m, int next[]) {
    next[1] = 0;
    int j = 1, k = 0;  // k 记录当前最长公共前后缀长度
    while (j < m) {
        if (k == 0 || T[j] == T[k]) {
            j++;
            k++;
            next[j] = k;   // next[j+1] = next[j] + 1（递推）
        } else {
            k = next[k];   // k 回退，类似 KMP 匹配过程
        }
    }
}

五、nextval 数组（优化的 next 数组）

next 的缺陷： 当 T[j] 失配且 T[next[j]] == T[j] 时，跳转到 next[j] 仍然会失配，浪费一次比较。

nextval 的改进： 如果 T[next[j]] == T[j]，则 nextval[j] = nextval[next[j]]，继续跳转，直到找到不同的字符或回到 0。

nextval 计算规则：

  1. nextval[1] = 0
  2. 对于 j ≥ 2：如果 T[next[j]] ≠ T[j]，则 nextval[j] = next[j]；如果 T[next[j]] == T[j]，则 nextval[j] = nextval[next[j]]

六、BF vs KMP 对比表

对比维度BF 算法KMP 算法
主串指针 i失配时回退不回退
模式串指针 j失配时回到 1失配时跳转到 next[j]
最坏时间复杂度O(n × m)O(n + m)
预处理无需计算 next 数组 O(m)
适用场景短模式串或偶尔匹配长模式串或多次匹配
空间复杂度O(1)O(m)（next 数组）

next 与 nextval 对比表：

对比维度next 数组nextval 数组
计算基础最长公共前后缀在 next 基础上优化
失配效率可能多次无效跳转避免无效跳转
匹配次数较多较少（更优）
计算复杂度O(m)O(m)
408 考试频率极高高（next 的升级版）

记忆辅助

  1. "BF 回退 i 和 j，KMP 只退 j 不退 i" — 最核心区别。KMP 的精髓是主串指针不回退。
  2. "next 看前缀，最长相等前后缀长度 +1" — 手动求 next 的口诀。
  3. "nextval 防重复，相等就跳过" — nextval 优化：如果跳转后字符相同，继续跳。
  4. "KMP 时间 O(n+m)，next 数组 O(m)" — 总时间 = 预处理 + 匹配 = O(m) + O(n+m) = O(n+m)。

例题精解

例题 1：手动求 next 数组

求模式串 T = "abaabcac" 的 next 数组。

解题四步法：

① 审题： T 长度 m = 8，逐位求 next[j]。

② 分析： next[1]=0, next[2]=1，后续看 T[1..j-1] 的最长公共前后缀。

③ 过程：

jT[j]T[1..j-1]最长公共前后缀长度next[j]
1a(空)——0（固定）
2b"a"无01（固定）
3a"ab"无01
4a"aba""a"12
5b"abaa""a"12
6c"abaab""ab"23
7a"abaabc"无01
8c"abaabca""a"12

next 数组：{0, 1, 1, 2, 2, 3, 1, 2}

④ 结论： 逐位分析最长公共前后缀长度即可得到 next 数组。关键位：j=6 时 "abaab" 的最长公共前后缀为 "ab"（长度 2），next[6] = 3。

例题 2：KMP 匹配过程模拟

主串 S = "ababaabaabcacbabc"，模式串 T = "abaabcac"，next = {0,1,1,2,2,3,1,2}，用 KMP 算法模拟匹配过程。

解题四步法：

① 审题： 用 KMP 算法在 S 中查找 T，展示匹配过程。

② 分析： 按 KMP 规则：匹配则 i++,j++；失配则 i 不动，j = next[j]。

③ 过程（关键步骤）：

主串 S: a b a b a a b a a b c a c b a b c
下标:   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

第1轮：i=1,j=1 → S[1]=a=T[1] ✓
       i=2,j=2 → S[2]=b=T[2] ✓
       i=3,j=3 → S[3]=a=T[3] ✓
       i=4,j=4 → S[4]=b≠T[4]=a ✗
       失配！j=next[4]=2，i 保持 4

第2轮：i=4,j=2 → S[4]=b=T[2] ✓
       i=5,j=3 → S[5]=a=T[3] ✓
       i=6,j=4 → S[6]=a=T[4] ✓
       i=7,j=5 → S[7]=b=T[5] ✓
       i=8,j=6 → S[8]=a≠T[6]=c ✗
       失配！j=next[6]=3，i 保持 8

第3轮：i=8,j=3 → S[8]=a=T[3] ✓
       i=9,j=4 → S[9]=a=T[4] ✓
       i=10,j=5 → S[10]=b=T[5] ✓
       i=11,j=6 → S[11]=c=T[6] ✓
       i=12,j=7 → S[12]=a=T[7] ✓
       i=13,j=8 → S[13]=c=T[8] ✓
       j=8>8，匹配成功！返回 i-m = 13-8 = 5

匹配成功位置：S 从下标 5 开始 = "abaabcac"

④ 结论： KMP 算法通过 next 数组避免了主串指针回退，总共比较约 14 次（远少于 BF 的最坏情况）。关键在于失配时 j 跳转到 next[j]，i 保持不变。

考情分析

维度说明
考频极高频，几乎每年必考
题型选择题（next 数组值判断、KMP 与 BF 对比）、综合题（手动求 next/nextval 数组 + 匹配过程）
命题趋势next 数组的手动计算是必考题；nextval 数组的求法是进阶考点
常见陷阱next[1]=0 和 next[2]=1 是固定值容易忘；最长公共前后缀不含字符串自身

易错点

  1. next[1] = 0，next[2] = 1，这是固定规定！ 不需要计算，直接写。失配时 j=next[1]=0 意味着 i 前进一位，j 回到开头重新开始。
  2. 最长公共前后缀不含字符串本身。 例如 "aba" 的前缀是 {"a", "ab"}，后缀是 {"a", "ba"}，公共部分是 {"a"}，长度为 1。
  3. KMP 的时间复杂度是 O(n + m)，不是 O(n × m)。 主串指针 i 不回退是关键，i 最多移动 n 次。
  4. nextval 的优化方向：如果 T[next[j]] == T[j]，则 nextval[j] = nextval[next[j]]。 这样可以跳过重复字符，减少无效比较。
  5. BF 的主串指针回退公式：i = i - j + 2。 这是回到"上次匹配起点的下一位"，容易计算错误。

来源标注

来源说明
王道考研2026 版数据结构讲义 · 第六章 查找
天勤考研数据结构高分笔记 · 查找部分
严蔚敏《数据结构（C 语言版）》第 4 章
教材参考《数据结构》（第 5 版）李春葆 · 串章节

考研全科复习资料 - 基于2026考研统考大纲

仅供学习参考