KMP算法（一）

一、简单模式匹配算法（BF 算法）

1. 什么是简单模式匹配算法

简单模式匹配算法，又称朴素模式匹配算法（Brute Force，简称 BF 算法），
是字符串匹配中最基本、最直观的一种方法。是指在主串中找到与模式串(想要搜索的某个字符串)相同的子串，并返回其所在的位置。这里采用定长顺序存储结构，给出一种不依赖于其他串操作的暴力匹配算法。

问题描述：

给定一个主串 S 和一个模式串 P，
判断 P 是否是 S 的子串，
若是，返回第一次匹配的位置。

/*
* 函数功能：朴素模式匹配（BF算法）
* 在主串 S 中查找模式串 T 第一次出现的位置
* 返回值：
* 若匹配成功，返回匹配起始下标（从1开始）
* 若匹配失败，返回 0
*/
int Index(SString S, SString T) {
int i = 1; // i 指向主串 S 当前比较的位置
int j = 1; // j 指向模式串 T 当前比较的位置

// 当主串和模式串均未越界时继续比较
while (i <= S.length && j <= T.length) {

// 当前字符相等，继续比较后续字符
if (S.ch[i] == T.ch[j]) {
i++;
j++;
}
// 当前字符不相等，模式串重新从头开始匹配
else {
// 主串指针回退到本次匹配起始位置的下一个字符
i = i – j + 2;
// 模式串指针回到起始位置
j = 1;
}
}

// 若模式串已全部匹配完成
if (j > T.length) {
// 返回匹配成功的起始位置
return i – T.length;
}
// 匹配失败
else {
return 0;
}
}

2. BF 算法的基本思想

核心思想一句话概括：

将模式串与主串的每一个可能起始位置进行逐字符比较，
一旦出现不匹配，
模式串回到起始位置，
主串从下一个字符重新开始比较。

3. BF 算法的指针定义

在算法执行过程中，通常设置两个指针：

• i：指向主串 S 中当前正在比较的字符

• j：指向模式串 P 中当前正在比较的字符

4. BF 算法的比较规则

5. BF 算法的图解过程（重点）

示例字符串

主串 S： a b a b a a b c a
下标： 0 1 2 3 4 5 6 7 8
模式 P： a b a a b
下标： 0 1 2 3 4

第一次匹配尝试

S: a b a b a a b c a
P: a b a a b
↑ ↑ ↑

• a == a ✓

• b == b ✓

• a == a ✓

此时比较到：

S[3] = b
P[3] = a → 失配

发生失配后的处理（关键）

i = i – j + 1 = 3 – 3 + 1 = 1
j = 0

含义：

• 主串回到下一个可能起点

• 模式串重新从第一个字符开始比较

第二次匹配尝试

S: a b a b a a b c a
a b a a b

继续逐字符比较，仍会失败。

不断重复上述过程

直到：

• 找到完全匹配

• 或主串剩余长度不足以匹配模式串

6. BF 算法的特点总结

优点

• 思想简单

• 易于理解和实现

缺点

• 存在大量重复比较

• 效率较低

7. 时间复杂度

• 最坏情况时间复杂度： O(n × m)

• 当主串和模式串中含有大量重复字符时，性能最差

8. BF 算法的本质问题

BF 算法在失配时
完全没有利用已匹配的部分信息，
导致主串和模式串频繁回退、重复比较。

二、KMP 算法（不涉及 next，仅算法思想）

1. 什么是 KMP 算法

KMP 算法是一种高效的字符串匹配算法，
由 Knuth、Morris、Pratt 三位学者提出。

提出目的：

在保证正确匹配的前提下，
减少无效比较，
提高字符串匹配效率。

2. KMP 算法的核心思想

一句话：

当匹配失败时，
不回退主串指针，
而是利用模式串自身的结构信息，
将模式串移动到一个“合理的位置”。

要了解模式串的结构，首先要弄清楚几个概念:前缀、后缀和部分匹配值。前缀是指除最后一个字符外，字符串的所有头部子串;后缀是指除第一个字符外，字符串的所有尾部子串;部分匹配值则是指字符串的前缀和后缀的最长相等前后缀长度。下面以'ababa'为例进行说明:'a'的前缀和后缀都为空集，最长相等前后缀长度为0。

2.1什么是前缀、后缀

以字符串 ababa 为例：

👉 所以：

字符串 "ababa" 的部分匹配值 = 3

• 前缀（不含自身）

  a
  ab
  aba
  abab

• 后缀（不含自身）

  baba
  aba
  ba
  a

  ---

  2.2公共前后缀

  前缀集合：{a, ab, aba, abab}
  后缀集合：{a, ba, aba, baba}

  公共元素：

  {a, aba}

• 公共元素有两个

• 最长公共前后缀是 "aba"

• 长度为 3

        2.3模式串每个位置的 PM 表是怎么来的

模式串：

a b a b a

我们不是一次算整个串，而是：

对模式串的每一个“前缀子串”分别求 PM 值

得到 PM 表

模式串: a b a b a
PM值: 0 0 1 2 3

那么：

模式串'ababa'的部分匹配值为00123

2.4 PM 表到底有什么作用？（重点）

当匹配失败时，用 PM 表决定模式串向右移动多少位，从而避免重复比较

3. KMP 与 BF 的根本区别

4. KMP 匹配过程图解（重点）

仍然使用相同示例：

主串 S： a b a b a a b c a
模式 P： a b a a b

前几步匹配

S: a b a b a a b c a
P: a b a a b
↑ ↑ ↑

前三个字符成功匹配。

发生失配

S[3] = b
P[3] = a → 失配

BF 的处理方式（对比）

模式串整体右移一位 从 P[0] 重新开始比较

KMP 的处理方式（关键）

不回退主串指针，
利用已匹配子串中
“前缀和后缀的公共部分”，
将模式串移动到仍可能匹配的位置。

示意：

S: a b a b a a b c a
P: a b a a b

本质理解

• 已经匹配的字符中一定包含某种重复结构

• 这些结构决定了：

  • 哪些位置一定不可能匹配

  • 哪些位置仍有可能匹配

• 因此可以跳过不必要的比较

5. KMP 算法——利用 PM 表进行匹配（完整过程）

第一趟匹配

主串： a b a b c a b c a c b a b
模式串： a b c a c
↑ ↑

a == a ✓

b == b ✓

a != c ✗ → 失配

已匹配字符数

已匹配 = 2 （"ab"）

查 PM 表

• 最后一个匹配字符是 'b'

• 'b' 对应的位置是第 2 位

• PM 值 = 0

关键公式

模式串右移位数 = 已匹配字符数 − 对应 PM 值

右移位数 = 2 − 0 = 2

右移后状态

主串: a b a b c a b c a c b a b
模式串: a b c a c

 注意：主串不回退

第二趟匹配

继续从当前位置比较：

• 重新比较

• 若再次失配，继续按同样规则查 PM 表、计算右移位数

对BF和KMP算法的本质理解

BF 算法的问题

• 失配后直接全部推倒重来

• 已经匹配的信息完全浪费

KMP（PM 表）的思想

• 已匹配的那一部分里
  已经包含了“前缀 = 后缀”的结构信息

• 这些结构说明：

  • 某些对齐方式一定不可能成功

  • 可以直接跳过

PM 表的意义

PM 表告诉我们：
在失配时，模式串最多能向右滑多少，而不漏掉任何可能的匹配

6. KMP 算法的优势

7. 小结

KMP 算法的高效性来源于：
在匹配前，对模式串进行分析，
记录每个位置失配后应移动到哪里。

这个分析结果
就体现在 next / nextval 数组 中。