全网最清晰的 KMP 算法讲解+图解，看完不会手把手教你写

前言：为什么你学不会 KMP？

• 大多数教程只会丢给你一个晦涩的 next 数组公式，却从没讲透：KMP
  的本质是在利用【重复最长前后缀】来‘白嫖’位移。本文不玩虚的，直接带你硬核拆解‘包含’与‘不包含’当前位置两种工业级流派
• 文中所有逻辑推演图均为作者本人手绘，如果这份干货能帮你少走弯路，麻烦点个赞，让更多人看到

本质说明

• 场景：查找子串在母串中出现的位置
• 本质：找某个可以重复出现的最长子串。backtrack_idx 既是这个重复出现子串的长度，也是下次某个位置对不上时，应该回溯的位置。
• backtrack_idx[]：本质就是利用了重复最长子串的对称性，对上了就+1，对不上就回溯到上一个重复最长子串

backtrack_table[] (不包含当前位置)

backtrack_table[i] 含义

• i 位置之前的子串的最长重复前后缀的长度
• 如果匹配失败，需要回退的位置 (巧妙的地方：回退的位置 = 最长前后缀前缀的最后一位的索引 + 1)

kmp (不包含当前位置)

kmp算法分类

不包含当前位置

前置说明

• backtrack_table[i]：不包含当前位置的前字串的最长重复前后缀长度
• backtrack_table[0] = -1
• backtrack_table[1] = 0

核心结构 – backtrack_table[]

算法步骤

• 初始化：设置 backtrack_table[0] = -1（强制位移标志）和 backtrack_table[1] = 0。
• 双指针探索：i 为当前计算位，backtrack_idx 为待匹配的前缀指针。
• 3 Cases：
  • Case 1 (Match): str[i-1] == str[backtrack_idx]。发现更长的对称轴，长度 +1，存入 backtrack_table[i++]。
  • Case 2 (Mismatch & Backtrack): 字符对不上，但 backtrack_idx 还没退到头。利用嵌套对称性，让 idx 跳到 backtrack_table[idx] 寻找更短的备用对称轴。
  • Case 3 (Total Mismatch): 退无可退（backtrack_idx == 0）。判定当前位置无重复模式，table[i++] = 0。

核心结构 – kmp

说明

• 优点：ptn_idx 始终单向递增，不进行低效的暴力回溯。

算法步骤

• 双指针：ptn_idx 扫描主串，sub_idx 扫描模式串。
• 动态跳转（The 3 Cases）：
  • Case 1 (Success): 字符匹配。两个指针同时 ++，向深处探索。
  • Case 2 (Soft Mismatch): 字符不配，但 sub_idx 还能退（!= -1）。查询 backtrack_table，让模式串像“抽屉”一样向右滑动，重新对齐对称轴。
  • Case 3 (Hard Mismatch): 首字符就不配（回退到了 -1）。判定当前主串位置无戏，sub_idx 归零，ptn_idx++ 强行开启下一格的尝试。
• 终点判定：如果 sub_idx 走完了模式串全程，匹配成功！

代码

int kmp(char *ptn, char *sub)
{
int ptn_l = strlen(ptn);
int sub_l = strlen(sub);

int ptn_idx = 0, sub_idx = 0;

int *bt_table = backtrack_table(sub);

while (ptn_idx < ptn_l && sub_idx < sub_l)
{
// case 1: ptn's current idx char matches sub's current idx char
if (ptn[ptn_idx] == sub[sub_idx])
{
ptn_idx++;
sub_idx++;
}

// case 2: doesn't match, but sub_idx can still go back
// ptn's current idx doesn't move and sub_idx go back, then check if they match
// backtrack_table[sub_idx] == -1 means, there is no repetitive substring can match, then move to case 3
// then we need to reset sub_idx to 0
// No potential match exists at the ptn's current position. then advance ptn_idx.
else if (bt_table[sub_idx] != –1)
{
sub_idx = bt_table[sub_idx];
}
// case 3: there is no repetitive substring can match
// sub_idx move to forefront and ptn's current idx move forward
else
{
sub_idx = 0;
ptn_idx++;
}
}
free(bt_table);
return sub_idx == sub_l ? ptn_idx – sub_l : –1;
}

int * backtrack_table(char *str)
{
int size = strlen(str);
int *backtrack_indices = (int *) malloc(size * sizeof(int));

if (size == 1) {
backtrack_indices[0] = –1;
return backtrack_indices;
}

backtrack_indices[0] = –1;
backtrack_indices[1] = 0;

int i = 2, backtrack_idx = 0;
while (i < size)
{
// case 1: current idx's char matches backtrack_idx's char
// Found a matching prefix-suffix pair, extend the length
if (str[i – 1] == str[backtrack_idx])
{
backtrack_indices[i++] = ++backtrack_idx;
}

// case 2: doen't match, but backtrack_idx can still go back
// Mismatch; backtrack to the previous longest repetitive prefix
// backtrack_idx > 0 means: there is still repetitive substring that can match
else if (backtrack_idx > 0)
{
backtrack_idx = backtrack_indices[backtrack_idx];
}

// case 3: backtrack_idx == 0, can't go back, then current idx doesn't have any repetitive prefix substring
// set current idx's backtrack_idx = 0, and move forward
else
{
backtrack_indices[i++] = 0;
}
}
return backtrack_indices;
}

包含当前位置

前置说明

• backtrack_table[i]：包含当前位置 $i$ 在内的前缀子串中，最长相等真前后缀的长度。
• 物理意义：它是当前子串的“对称性”度量。如果 $i$ 位置匹配失败，则根据前一个位置 $i-1$ 的对称性信息来决定 backtrack_idx 应该跳到哪里。
• 初始状态：backtrack_table[0] = 0。

核心结构 – backtrack_table[]

算法步骤

• 初始化：table[0] = 0。i 为当前计算位（从 1 开始），backtrack_idx 为待匹配的前缀指针（从 0 开始）。
• 双指针探索：i 负责遍历模式串，backtrack_idx 负责根据匹配情况缩放对称轴。
• 3 Cases：
  • Case 1 (Match): ptn[i] == ptn[backtrack_idx]。发现更长的对称关系。table[i++] = ++backtrack_idx;
  • Case 2 (Mismatch & Backtrack): 字符对不上且 backtrack_idx > 0。利用嵌套对称性，令 backtrack_idx = table[backtrack_idx – 1]。
  • Case 3 (Total Mismatch): backtrack_idx == 0 且字符仍不对。判定当前位置无重复模式，table[i++] = 0;

核心结构 – kmp

说明

• 优点：逻辑极其紧凑，不需要 -1 哨兵，通过 while (idx > 0) 优雅地处理回溯终点。

算法步骤

• 双指针：ptn_idx 扫描主串（Subject），sub_idx 扫描模式串（Pattern）。
• 动态跳转 (The 3 Cases)：
  • Case 1 (Success): sub[ptn_idx] == ptn[sub_idx]。匹配成功，双指针同步 ++。
  • Case 2: 字符不配且 sub_idx > 0。查询 table[sub_idx – 1]，获取前一位的对称长度，将模式串重对齐。
  • Case 3: sub_idx == 0 且首字母就不配。模式串不动，主串前进 ptn_idx++。
• 终点判定：如果 sub_idx 达到模式串长度，匹配成功。

代码

int* backtrack_table(char* str) {
int size = strlen(str);
int* backtrack_table = (int*)malloc(sizeof(int) * size);
if (size == 0) return backtrack_table;

backtrack_table[0] = 0; // 单个字符无前后缀
int i = 1, backtrack_idx = 0;

while (i < size) {
// Case 1: Match! Extend the repetitive length
if (str[i] == str[backtrack_idx]) {
backtrack_table[i++] = ++backtrack_idx;
}
// Case 2: Mismatch, but backtrack_idx can still fallback
// 关键逻辑：查询前一个已知安全位置的对称长度
else if (backtrack_idx > 0) {
backtrack_idx = backtrack_table[backtrack_idx – 1];
}
// Case 3: Totally mismatch, set 0 and move forward
else {
backtrack_table[i++] = 0;
}
}
return backtrack_table;
}

int kmp(char* ptn, char* sub) {
int ptn_l = strlen(ptn);
int sub_l = strlen(sub);
if (sub_l == 0) return 0;

// 对子串 sub 进行预分析
int* bt_table = backtrack_table(sub);
int ptn_idx = 0, sub_idx = 0;

while (ptn_idx < ptn_l && sub_idx < sub_l) {
// Case 1: Match. Both pointers move forward
if (ptn[ptn_idx] == sub[sub_idx]) {
ptn_idx++;
sub_idx++;
}
// Case 2: Mismatch. sub_idx backtracks using the table
// 本质：sub_idx 失败，查询已验证的 sub_idx – 1 状态
else if (sub_idx > 0) {
sub_idx = bt_table[sub_idx – 1];
}
// Case 3: Hard Mismatch. Advance main string pointer
else {
ptn_idx++;
}
}

free(bt_table);
// 判定是否匹配完成：sub_idx 走完了子串全程
return (sub_idx == sub_l) ? (ptn_idx – sub_l) : –1;
}

不包含当前位置 & 包含当前位置

对比

• 不包含当前位置
  • backtrack_table[i]：不包含当前位置的前字串的最长重复前后缀长度
  • backtrack_table[0] = -1
  • backtrack_table[1] = 0
• 包含当前位置
  • backtrack_table[i]：包含当前位置 $i$ 在内的前缀子串中，最长相等真前后缀的长度。
  • 意义：它是当前子串的“对称性”度量。如果 $i$ 位置匹配失败，则根据前一个位置 $i-1$ 的对称性信息来决定 backtrack_idx 应该跳到哪里。
  • i – 1的说明：如果 i 位置匹配失败，那么 backtrack_table[i] = 0，也就是说最长重复前后缀的长度 (跳转位置) 是在 i – 1，也就是backtrack_table[i – 1] 的值
  • 初始状态：backtrack_table[0] = 0。

例子

子串 sub = "ABABC"，主串 ptn = "ABABDABABC"

不包含当前位置 backtrack_table[] 构建

backtrack_table [i] 存的是 $i$ 之前的子串信息。

• i=0: -1 (强制移动)

• i=1: 0 (子串 “A”)

• i=2: 0 (子串 “AB”)

• i=3: 1 (子串 “ABA” -> “A” 对称)

• i=4: 2 (子串 “ABAB” -> “AB” 对称)

  结果：backtrack_table = [-1, 0, 0, 1, 2]

包含当前位置 backtrack_table[] 构建

backtrack_table [i] 存的是截止到 $i$ 的子串信息。

• i=0: 0 (子串 “A”)

• i=1: 0 (子串 “AB”)

• i=2: 1 (子串 “ABA” -> “A” 对称)

• i=3: 2 (子串 “ABAB” -> “AB” 对称)

• i=4: 0 (子串 “ABABC” -> 无对称)

  结果：backtrack_table = [0, 0, 1, 2, 0]

kmp匹配失败

• 主串 ptn: A B A B D …
• 子串sub: A B A B C
• 当前索引: ptn_idx = 4, sub_idx = 4 (指向字符 D vs C)

不包含当前位置回溯

backtrack_table = [-1, 0, 0, 1, 2]

• backtrack_table[4] = 2。
• 动作：sub_idx = 2。直接跳到子串的索引 2（字符 A）去和主串的 D 比较。
• 说明：backtrack_table[4] = 2 ：在 C 之前的 ABAB 里，前缀和后缀重合了 2 位。

包含当前位置回溯

backtrack_table = [0, 0, 1, 2, 0]

• backtrack_table[4] = 0。
• 说明：如果 i 位置匹配失败，那么 backtrack_table[i] = 0，也就是说最长重复前后缀的长度 (跳转位置) 是在 i – 1，也就是backtrack_table[i – 1] 的值
• 动作：查看 table[4 – 1]，即 table[3] = 2，回跳到 2 位置

结语

• 文中所有逻辑推演图均为作者本人手绘，如果这篇文章真的让你有一种“拨云见日”的感觉，麻烦动动小手，给作者留个赞。你的每一个点赞，都是对我这份“硬核原创”最直接的认可！
• 本人水平有限，文中虽经反复推敲，但难免有疏漏或表述不当之处。若各位同仁在阅读中发现纰漏，恳请在评论区指正，咱们共同探讨、共同进步