一、最基础概念

1. 字符串匹配

问题：给一段很长的文本（主串），一段要找的短文本（模式串），判断短文本是否出现在长文本里，找到它的位置。举例：

• 主串：abcabababc（长文本）
• 模式串：ababc（要找的单词）

2. 暴力匹配（最原始的方法）

逻辑：长文本从第 1 位开始，和短文本一个字符一个字符挨个对。

• 对上了：继续下一个；
• 对不上：长文本往后挪 1 位，短文本从头重新开始比对。

缺点：长文本的指针会往回退、重复比对，前面已经匹配成功的内容全部浪费，速度很慢。

二、KMP 是什么（正式概念）

KMP 算法：是一种高效的字符串匹配算法。全称：Knuth‑Morris‑Pratt 算法，三位大佬名字缩写。

核心目标：解决暴力匹配 “重复比对、回头浪费时间” 的问题。

核心思想（一句话概念）

主串（长文本）的查找指针永远不后退，只利用模式串自身的重复规律，让模式串跳跃到合适位置，继续匹配，不用从头重来。

三、3 个必须懂的核心概念（KMP 灵魂）

1. 前缀

对一个字符串，从开头取、不包含最后一个字符的所有子串。例：字符串 abab前缀：a、ab、aba

2. 后缀

对一个字符串，从结尾取、不包含第一个字符的所有子串。例：字符串 abab后缀：b、ab、bab

3. 最长相等前后缀

对字符串的某一段，最长的、一模一样的前缀和后缀。

例：abab

前缀ab = 后缀ab → 最长相等前后缀长度 = 2

作用：匹配失败时，我们不用从头比，直接跳到这个重复的位置继续比。

四、next 数组（KMP 的工具概念）

概念

next 数组：提前给模式串算好的一张 “跳转表”。数组里的每一个数，表示：模式串在这个位置匹配失败时，应该跳到第几个字符继续匹配。

规则：next[i] = 模式串前 i 个字符的最长相等前后缀长度。

举例：模式串 ababc

字符	a	b	a	b	c
next	0	0	1	2	0

含义：

• 第 3 个a匹配失败：跳到第 1 个a
• 第 4 个b匹配失败：跳到第 2 个b
• 其余失败：从头开始

五、KMP 完整工作概念（三步走）

1. 预处理模式串：算出 next 跳转数组，找出自身重复规律；
2. 开始匹配：主串指针一直往后走，绝不回头；
3. 匹配失败时：主串不动，模式串根据 next 数组直接跳跃，不用从头比对。

六、时间复杂度概念（简单记）

• 暴力匹配：O(n×m)，长文本 × 短文本，数据越大越慢；
• KMP 算法：O(n+m)，线性时间，只走一遍主串、一遍模式串，速度极快。

七、终极通俗总结（概念浓缩）

KMP = 提前找短单词自己重复的部分 → 做成跳转表 → 长句子不回头，错了就按表跳着找。

c++实现

• 先求 next 数组（跳转表）
• 再进行 KMP 字符串匹配

代码对应概念（一一对应）

1. 前缀、后缀、最长相等前后缀在 getNext 函数里，j 就是用来找最长相等前后缀的。
2. next 数组就是跳转表，告诉模式串失败时跳到哪。
3. 主串指针不回头匹配函数里的 i 只递增，永远不会往回走，这就是 KMP 快的核心。
4. 暴力 vs KMP暴力法 i 会回退；KMP 的 i 全程只前进。

对应主串：a b a b a b c，从下标 2 开始就是 ababc。

时间复杂度

• 求 next：O(m)
• 匹配：O(n)
• 总复杂度：O(n+m)