在字符串匹配问题中暴力匹配算法BF虽然简单但效率极低 —— 每次字符不匹配文本串和模式串的指针都要大量回溯时间复杂度达到 O (n*m)。而KMP 算法通过构建前缀表next 数组巧妙避免了重复比较将时间复杂度优化到 O (nm)是字符串匹配的经典高效算法。一、核心思想用前缀表避免重复比较暴力匹配的痛点比如文本串aabaabaaf模式串aabaaf当匹配到第 5 位bvsf不匹配时暴力算法会把文本串指针回退到第 1 位模式串指针回退到 0重新开始比较。KMP 的解决思路提前记录模式串中每个位置的最长相等前后缀长度即前缀表当字符不匹配时模式串指针不需要回到 0而是回退到最长相等前后缀的末尾位置继续比较从而跳过大量重复的匹配步骤。举个例子模式串aabaaf中前 5 位aabaa的最长相等前后缀是aa所以当第 5 位不匹配时模式串指针可以直接回退到第 2 位aa的末尾而不是从头开始。二、next 数组前缀表构建代码 逐行解析next 数组的本质next[i]表示模式串s[0..i]中最长相等 ** 前缀不包含最后一个字符和后缀不包含第一个字符** 的长度。1. 变量含义i后缀字符串的末尾从 1 开始遍历因为第一个字符没有前后缀j前缀字符串的末尾同时也是当前最长相等前后缀的长度next[j] 0第一个字符的最长相等前后缀长度为 0没有前后缀2. 代码实现c运行void getNext(int* next, char* s) { int len strlen(s); // 模式串长度 int i 1; // 后缀末尾从1开始 int j 0; // 前缀末尾初始为0 next[j] 0; // 第一个字符的next值固定为0 for (i 1; i len; i) { // 1. 前后缀不相等时j回退到之前的最长匹配位置 while (j 0 s[i] ! s[j]) { j next[j - 1]; // 核心回退到next[j-1]不是j-- } // 2. 前后缀相等时最长长度1 if (s[i] s[j]) { j; } // 3. 记录当前位置的最长相等前后缀长度 next[i] j; } }3. 举个栗子计算aabaaf的 next 数组表格索引 i012345字符 saabaafnext[i]010120i1字符 as [1] s [0] → j1 → next [1]1i2字符 bs [2] ! s [1] → j 回退到 next [0]0仍不相等 → next [2]0i3字符 as [3] s [0] → j1 → next [3]1i4字符 as [4] s [1] → j2 → next [4]2i5字符 fs [5] ! s [2] → j 回退到 next [1]1仍不等 → 回退到 next [0]0仍不等 → next [5]0三、KMP 匹配过程代码 逐行解析利用构建好的 next 数组在文本串和模式串匹配时避免文本串指针回溯只回退模式串指针。1. 变量含义i文本串指针从 0 开始永不回溯j模式串指针不匹配时回退到 next [j-1]2. 代码实现c运行int kmpSearch(char* text, char* pattern) { int n strlen(text); // 文本串长度 int m strlen(pattern); // 模式串长度 int i 0, j 0; // 文本串/模式串指针 if (m 0) return 0; // 空模式串默认匹配位置0 // 动态分配next数组避免固定长度限制 int* next (int*)malloc(m * sizeof(int)); if (next NULL) return -1; // 内存分配失败处理 getNext(next, pattern); // 构建next数组 for (i 0; i n; i) { // 1. 字符不匹配时模式串指针回退 while (j 0 text[i] ! pattern[j]) { j next[j - 1]; // 核心和next数组构建时的回退逻辑一致 } // 2. 字符匹配时模式串指针后移 if (text[i] pattern[j]) { j; } // 3. 模式串完全匹配返回起始位置 if (j m) { free(next); // 释放内存避免泄漏 return i - m 1; // 起始索引 当前i - 模式串长度 1 } } free(next); // 未匹配时也要释放内存 return -1; // 未找到匹配 }3. 匹配示例文本串aabaabaaf模式串aabaaf当 i5文本串字符bj5模式串字符f时不匹配 → j 回退到 next [4]2继续比较text [5] bvs pattern[2] b→ 匹配j3后续继续匹配直到 j6模式串长度为 6说明匹配成功返回起始位置 i8-613四、KMP 算法易错点总结面试 / 编码必看next 数组构建时的回退逻辑错误❌ 错误写法j--暴力回退失去 KMP 的优化意义✅ 正确写法j next[j - 1]利用前缀表回退到最长匹配位置next 数组的起始索引错误❌ 错误i从 0 开始遍历会重复计算第一个字符的 next 值✅ 正确i从 1 开始遍历next[0]手动初始化为 0内存管理问题❌ 错误free(next)写在循环内导致内存提前释放野指针访问崩溃✅ 正确在匹配成功 / 循环结束后统一释放内存❌ 错误未处理malloc返回NULL的情况内存分配失败时访问空指针✅ 正确添加if (next NULL)判断匹配成功后的返回值计算❌ 错误返回i - m少加 1索引从 0 开始✅ 正确返回i - m 1起始位置是当前 i 减去模式串长度再加 1控制台中文乱码问题原因VS 默认编码和控制台编码不匹配✅ 解决在main函数开头添加setlocale(LC_ALL, chs);需包含locale.h头文件空模式串处理✅ 必须提前判断if (m 0) return 0;避免后续逻辑出错五、完整可运行代码含编码修复c运行#include stdio.h #include string.h #include stdlib.h #include locale.h // 解决中文乱码 // 构建next数组前缀表 void getNext(int* next, char* s) { int len strlen(s); int i 1; int j 0; next[0] 0; for (i 1; i len; i) { while (j 0 s[i] ! s[j]) { j next[j - 1]; } if (s[i] s[j]) { j; } next[i] j; } } // KMP匹配函数 int kmpSearch(char* text, char* pattern) { int n strlen(text); int m strlen(pattern); int i 0, j 0; if (m 0) return 0; int* next (int*)malloc(m * sizeof(int)); if (next NULL) return -1; getNext(next, pattern); for (i 0; i n; i) { while (j 0 text[i] ! pattern[j]) { j next[j - 1]; } if (text[i] pattern[j]) { j; } if (j m) { free(next); return i - m 1; } } free(next); return -1; } int main() { setlocale(LC_ALL, chs); // 解决VS控制台中文乱码 char text[] aabaabaaf; char pattern[] aabaaf; int index kmpSearch(text, pattern); if (index ! -1) { printf(匹配成功起始位置%d\n, index); } else { printf(未找到匹配\n); } return 0; }六、总结KMP 算法的核心就是前缀表next 数组通过记录最长相等前后缀避免了暴力匹配的重复回溯。只要记住next 数组构建i从 1 开始j回退到next[j-1]匹配过程i永不回溯j回退到next[j-1]易错点重点关注回退逻辑、内存管理和返回值计算这样复习时看一遍就能快速回忆起 KMP 的核心逻辑和编码细节