在编程开发中字符串模式匹配是非常基础且常用的操作核心需求是在一个主字符串str中查找指定子字符串pattern模式串的首次出现位置。本文将介绍两种经典的模式匹配算法 —— 暴力匹配算法和 KMP 算法通过 C 语言代码实现深入解析其原理、执行过程及优缺点帮助大家理解两种算法的核心差异。一、暴力匹配算法BF 算法暴力匹配算法Brute Force也叫朴素匹配算法是最简单的字符串模式匹配方法核心思路是逐位比对失配回溯通过两层循环依次尝试主字符串中所有可能的起始位置与模式串进行匹配。1. 算法核心原理设主字符串长度为n模式串长度为m主字符串的匹配起始位置i从 0 开始最大到n-m超出后剩余字符不足以匹配模式串。模式串的比对指针j从 0 开始逐位比较str[i]和pattern[j]。若字符相等i和j同时后移继续比对下一位若字符不相等主字符串指针回溯到本次起始位置的下一位i i - j模式串指针j重置为 0重新开始匹配。若模式串指针j遍历完所有字符j m说明匹配成功返回本次匹配的起始位置i - j若主字符串遍历完仍未匹配返回 - 1。2. C 语言代码实现#include stdio.h #include string.h /** * 暴力字符串模式匹配函数 * param str 主字符串被查找的长串 * param pattern 模式串要查找的短串 * return 找到返回模式串在主串中第一次出现的起始下标 * 没找到返回 -1 */ int strMatch(char* str, char* pattern) { // 获取主字符串的长度 int n strlen(str); // 获取模式串的长度 int m strlen(pattern); // 外层循环控制主串的【匹配起始位置】i // 主串最多只能从 n-m 位置开始匹配否则剩余字符不够匹配模式串 for (int i 0; i (n - m); i) { // 每次重新匹配模式串指针 j 都从 0 开始 int j 0; // 内层循环逐字符对比 while(j m) { // 如果当前主串字符 模式串字符两个指针同时向后移动 if (str[i] pattern[j]) { i; // 主串指针后移 j; // 模式串指针后移 } // 字符不相等发生失配需要回溯 else { // 关键主串 i 回溯到【本次匹配起始位置的下一位】 i i - j; // 退出内层循环重新开始下一轮匹配 break; } } // 如果 j 走完了整个模式串说明完全匹配成功 if (j m) { // 返回匹配的起始位置i - j 是因为 i 已经后移过了 return i - j; } } // 循环结束都没找到返回 -1 return -1; } // 主函数测试暴力匹配算法 int main(int argc, char const *argv[]) { // 定义主串 char* str abcabaabcabc; // 定义要查找的模式串 char* pattern abaa; // 调用匹配函数 int pos strMatch(str, pattern); // 输出结果找到则输出下标没找到输出 -1 printf(模式串出现的位置%d\n, pos); return 0; }3. 算法特点优点逻辑简单代码实现直观无需额外的预处理步骤适合短字符串的简单匹配场景。缺点效率低下存在大量的无效回溯。当主字符串和模式串存在部分匹配的前缀时主字符串指针需要回退到初始位置重新比对最坏时间复杂度为O(n*m)n 为主串长度m 为模式串长度。测试结果上述代码中主串abcabaabcabc与模式串abaa无匹配最终输出-1。二、KMP 算法KMP 算法由 Knuth、Morris、Pratt 三位学者提出是对暴力匹配算法的优化核心解决了暴力算法中主字符串指针回溯的问题通过对模式串进行预处理生成 next 数组记录模式串失配时的回退位置让主字符串指针始终只向后移动大幅提升匹配效率。1. 算法核心原理KMP 算法的核心是next 数组next 数组的长度与模式串一致next[j]表示模式串中第j位字符失配时模式串指针需要回退到的位置本质是找模式串前缀和后缀的最长相等子串长度。整个算法分为两个阶段预处理阶段遍历模式串生成 next 数组记录每个位置的失配回退点。匹配阶段主串指针i和模式串指针j均从 0 开始逐位比对若失配根据 next 数组让模式串指针j回退主串指针i保持不变若匹配成功两个指针同时后移直到匹配完成或主串遍历结束。2. 关键next 数组的生成next 数组的生成规则本文实现为基础版 next 数组初始化next[0] -1模式串首位失配主串指针后移模式串指针回退到 -1这是人为定义的边界条件同时定义两个指针i为模式串的遍历指针从 0 开始负责逐个遍历模式串字符j为前缀后缀匹配指针初始值为 - 1负责记录当前位置前的模式串中前缀和后缀的最长相等子串长度也是失配时的回退目标位置。随后进入循环遍历模式串i 模式串长度m核心逻辑分两种情况当j -1或pattern[i] pattern[j]时j -1表示当前回到匹配起点无任何前缀后缀可匹配而pattern[i] pattern[j]表示当前字符匹配成功说明找到更长的相等前后缀。此时将i和j同时向后移动一位再将next[i]赋值为j这个j值就是模式串第i位字符失配时需要回退到的目标位置。当pattern[i] ! pattern[j]时说明当前字符匹配失败无法形成更长的相等前后缀此时需要让j根据已生成的 next 数组向前回退即j next[j]重新寻找更短的相等前后缀直到满足j -1或字符匹配成功为止。整个 next 数组的生成过程本质是模式串自己和自己做匹配通过不断寻找前后缀的最长相等子串提前记录所有位置的失配回退点为后续的主串匹配阶段做预处理这一步的时间复杂度为O(m)m 为模式串长度。3. C 语言代码实现带完整详细注释#include stdio.h #include string.h /** * 预处理模式串生成KMP核心的next数组 * param pattern 待处理的模式串 * param next 用于存储回退位置的next数组 */ void getNext(char* pattern, int* next) { int m strlen(pattern); // 获取模式串长度 int i 0; // 模式串遍历指针从0开始 int j -1; // 前后缀匹配指针初始为-1边界条件 next[0] -1; // next数组首位固定为-1人为定义的失配边界 // 遍历模式串生成完整的next数组i m 避免数组越界 while(i m) { // 边界情况 或 当前字符匹配成功拓展相等前后缀 if (j -1 || pattern[i] pattern[j]) { i; // 模式串遍历指针后移 j; // 前后缀匹配长度1回退位置后移 next[i] j; // 记录当前位置的失配回退点 } else { j next[j]; // 字符匹配失败j根据next数组向前回退 } } } /** * KMP算法核心匹配函数 * param str 主字符串被查找的长串 * param pattern 模式串要查找的短串 * return 匹配成功返回模式串在主串中首次出现的起始下标 * 匹配失败返回-1 */ int kmp(char* str, char* pattern) { int i 0; // 主串遍历指针从不回溯仅向后移动 int j 0; // 模式串遍历指针失配时根据next回退 int next[100]; // 定义next数组存储模式串失配回退点 getNext(pattern, next); // 预处理模式串生成next数组 int n strlen(str); // 获取主串长度 int m strlen(pattern); // 获取模式串长度 // 主串和模式串均未遍历完时继续匹配 while(i n j m) { // 模式串回退到边界 或 当前主串与模式串字符匹配成功 if (j -1 || str[i] pattern[j]) { i; // 主串指针后移继续匹配下一位 j; // 模式串指针后移继续匹配下一位 } else { j next[j]; // 字符失配主串指针不动模式串指针按next回退 } } // 若模式串指针遍历完所有字符说明完全匹配成功 if (j m) { return i - j; // 计算并返回模式串在主串中的起始下标 } else { return -1; // 匹配失败返回-1 } } // 主函数测试KMP算法匹配效果 int main(int argc, char const *argv[]) { char* str abaabaabacacaabaabcc; // 定义主字符串 char* pattern abaabc; // 定义要查找的模式串 printf(%d\n, kmp(str, pattern)); // 调用KMP函数打印匹配结果 return 0; }4. 算法匹配执行示例以上述测试代码为例主串为abaabaabacacaabaabcc模式串为abaabc经getNext函数预处理后生成的 next 数组为[-1,0,0,1,2,0]。匹配过程中主串指针i始终向后移动当遇到字符失配时模式串指针j根据 next 数组回退到对应位置而非重置为 0最终会在主串下标 5的位置匹配到模式串因此代码运行结果输出5。5. 算法特点优点彻底解决了暴力算法的无效回溯问题主串指针仅遍历一次预处理阶段时间复杂度 O (m)匹配阶段时间复杂度 O (n)整体时间复杂度为 O (nm)n 为主串长度m 为模式串长度在长字符串匹配场景下效率远高于暴力算法。缺点基础版 next 数组存在少量冗余回退可通过优化 next 数组为 nextval 数组解决需要额外的数组空间存储 next 数组空间复杂度为 O (m)属于空间换时间的经典算法设计思路。三、暴力算法与 KMP 算法核心对比对比维度暴力匹配算法BFKMP 算法核心思路逐位匹配失配后主串、模式串指针均回溯预处理模式串生成 next 数组失配仅模式串指针回退主串指针不回溯时间复杂度最坏 O (n*m)最好 O (n)整体 O (nm)无最坏情况效率稳定空间复杂度O (1)无需额外辅助空间O (m)需要存储 next 数组实现难度逻辑简单代码易实现需理解 next 数组原理实现稍复杂适用场景短字符串、简单匹配场景对效率要求不高长字符串、高频匹配场景对效率要求较高四、408真题演练KMP 算法的核心是next 数组失配时通过next数组回退模式串指针j主串指针i保持不变。确定模式串tt abaababc索引从 0 开始索引 j01234567字符 t [j]abaababc计算模式串的next数组next[j]表示t[0..j-1]的最长公共前后缀长度。next[0] -1约定next[1] 0子串a无前后缀next[2] 0子串abnext[3] 1子串aba最长公共前后缀为anext[4] 2子串abaa最长公共前后缀为abnext[5] 2子串abaab最长公共前后缀为abnext[6] 3子串abaaba最长公共前后缀为abanext[7] 4子串abaabab最长公共前后缀为abab完整next数组[-1, 0, 0, 1, 2, 2, 3, 4]失配处理题目中第一次失配时i5, j5根据 KMP 规则主串指针i保持不变即i5模式串指针j回退到next[j] next[5] 2答案C步骤 1计算模式串S的next数组模式串S abaabc索引从 0 开始索引 j012345字符 S [j]abaabcnext[j]定义为子串S[0..j-1]的最长公共前后缀长度约定next[0] -1next[0] -1next[1] 0子串a无前后缀next[2] 0子串abnext[3] 1子串aba最长公共前后缀为anext[4] 2子串abaa最长公共前后缀为abnext[5] 2子串abaab最长公共前后缀为ab最终next数组[-1, 0, 0, 1, 2, 2]步骤 2逐次模拟 KMP 匹配过程主串T abaabaab cababaabc模式串S abaabc初始化i0主串指针、j0模式串指针比较次数count0。第 1~6 次比较T[0]avsS[0]a→ 匹配i1,j1count1T[1]bvsS[1]b→ 匹配i2,j2count2T[2]avsS[2]a→ 匹配i3,j3count3T[3]avsS[3]a→ 匹配i4,j4count4T[4]bvsS[4]b→ 匹配i5,j5count5T[5]avsS[5]c→ 失配count6失配处理j next[5] 2i保持5第 7 次比较T[5]avsS[2]a→ 匹配i6,j3count7第 8~11 次比较T[6]avsS[3]a→ 匹配i7,j4count8T[7]bvsS[4]b→ 匹配i8,j5count9T[8]cvsS[5]c→ 匹配i9,j6count10此时j6等于模式串长度6匹配成功 ✅答案B五、总结字符串模式匹配中暴力算法是最基础的实现方式凭借逻辑简单的优势在短字符串匹配中仍有一定应用而 KMP 算法通过预处理生成 next 数组的巧妙设计用少量的空间开销换来了时间效率的大幅提升解决了暴力算法的无效回溯问题成为长字符串模式匹配的经典算法。理解 KMP 算法的关键在于掌握next 数组的生成原理—— 本质是模式串的自匹配记录每个位置的最长相等前后缀长度这也是 KMP 算法的核心精髓。掌握这两种算法能为后续学习更高效的字符串匹配算法如 BM 算法、Sunday 算法打下坚实的基础。
【数据结构】字符串模式匹配：暴力算法与 KMP 算法实现与解析
发布时间：2026/6/22 2:59:08
在编程开发中字符串模式匹配是非常基础且常用的操作核心需求是在一个主字符串str中查找指定子字符串pattern模式串的首次出现位置。本文将介绍两种经典的模式匹配算法 —— 暴力匹配算法和 KMP 算法通过 C 语言代码实现深入解析其原理、执行过程及优缺点帮助大家理解两种算法的核心差异。一、暴力匹配算法BF 算法暴力匹配算法Brute Force也叫朴素匹配算法是最简单的字符串模式匹配方法核心思路是逐位比对失配回溯通过两层循环依次尝试主字符串中所有可能的起始位置与模式串进行匹配。1. 算法核心原理设主字符串长度为n模式串长度为m主字符串的匹配起始位置i从 0 开始最大到n-m超出后剩余字符不足以匹配模式串。模式串的比对指针j从 0 开始逐位比较str[i]和pattern[j]。若字符相等i和j同时后移继续比对下一位若字符不相等主字符串指针回溯到本次起始位置的下一位i i - j模式串指针j重置为 0重新开始匹配。若模式串指针j遍历完所有字符j m说明匹配成功返回本次匹配的起始位置i - j若主字符串遍历完仍未匹配返回 - 1。2. C 语言代码实现#include stdio.h #include string.h /** * 暴力字符串模式匹配函数 * param str 主字符串被查找的长串 * param pattern 模式串要查找的短串 * return 找到返回模式串在主串中第一次出现的起始下标 * 没找到返回 -1 */ int strMatch(char* str, char* pattern) { // 获取主字符串的长度 int n strlen(str); // 获取模式串的长度 int m strlen(pattern); // 外层循环控制主串的【匹配起始位置】i // 主串最多只能从 n-m 位置开始匹配否则剩余字符不够匹配模式串 for (int i 0; i (n - m); i) { // 每次重新匹配模式串指针 j 都从 0 开始 int j 0; // 内层循环逐字符对比 while(j m) { // 如果当前主串字符 模式串字符两个指针同时向后移动 if (str[i] pattern[j]) { i; // 主串指针后移 j; // 模式串指针后移 } // 字符不相等发生失配需要回溯 else { // 关键主串 i 回溯到【本次匹配起始位置的下一位】 i i - j; // 退出内层循环重新开始下一轮匹配 break; } } // 如果 j 走完了整个模式串说明完全匹配成功 if (j m) { // 返回匹配的起始位置i - j 是因为 i 已经后移过了 return i - j; } } // 循环结束都没找到返回 -1 return -1; } // 主函数测试暴力匹配算法 int main(int argc, char const *argv[]) { // 定义主串 char* str abcabaabcabc; // 定义要查找的模式串 char* pattern abaa; // 调用匹配函数 int pos strMatch(str, pattern); // 输出结果找到则输出下标没找到输出 -1 printf(模式串出现的位置%d\n, pos); return 0; }3. 算法特点优点逻辑简单代码实现直观无需额外的预处理步骤适合短字符串的简单匹配场景。缺点效率低下存在大量的无效回溯。当主字符串和模式串存在部分匹配的前缀时主字符串指针需要回退到初始位置重新比对最坏时间复杂度为O(n*m)n 为主串长度m 为模式串长度。测试结果上述代码中主串abcabaabcabc与模式串abaa无匹配最终输出-1。二、KMP 算法KMP 算法由 Knuth、Morris、Pratt 三位学者提出是对暴力匹配算法的优化核心解决了暴力算法中主字符串指针回溯的问题通过对模式串进行预处理生成 next 数组记录模式串失配时的回退位置让主字符串指针始终只向后移动大幅提升匹配效率。1. 算法核心原理KMP 算法的核心是next 数组next 数组的长度与模式串一致next[j]表示模式串中第j位字符失配时模式串指针需要回退到的位置本质是找模式串前缀和后缀的最长相等子串长度。整个算法分为两个阶段预处理阶段遍历模式串生成 next 数组记录每个位置的失配回退点。匹配阶段主串指针i和模式串指针j均从 0 开始逐位比对若失配根据 next 数组让模式串指针j回退主串指针i保持不变若匹配成功两个指针同时后移直到匹配完成或主串遍历结束。2. 关键next 数组的生成next 数组的生成规则本文实现为基础版 next 数组初始化next[0] -1模式串首位失配主串指针后移模式串指针回退到 -1这是人为定义的边界条件同时定义两个指针i为模式串的遍历指针从 0 开始负责逐个遍历模式串字符j为前缀后缀匹配指针初始值为 - 1负责记录当前位置前的模式串中前缀和后缀的最长相等子串长度也是失配时的回退目标位置。随后进入循环遍历模式串i 模式串长度m核心逻辑分两种情况当j -1或pattern[i] pattern[j]时j -1表示当前回到匹配起点无任何前缀后缀可匹配而pattern[i] pattern[j]表示当前字符匹配成功说明找到更长的相等前后缀。此时将i和j同时向后移动一位再将next[i]赋值为j这个j值就是模式串第i位字符失配时需要回退到的目标位置。当pattern[i] ! pattern[j]时说明当前字符匹配失败无法形成更长的相等前后缀此时需要让j根据已生成的 next 数组向前回退即j next[j]重新寻找更短的相等前后缀直到满足j -1或字符匹配成功为止。整个 next 数组的生成过程本质是模式串自己和自己做匹配通过不断寻找前后缀的最长相等子串提前记录所有位置的失配回退点为后续的主串匹配阶段做预处理这一步的时间复杂度为O(m)m 为模式串长度。3. C 语言代码实现带完整详细注释#include stdio.h #include string.h /** * 预处理模式串生成KMP核心的next数组 * param pattern 待处理的模式串 * param next 用于存储回退位置的next数组 */ void getNext(char* pattern, int* next) { int m strlen(pattern); // 获取模式串长度 int i 0; // 模式串遍历指针从0开始 int j -1; // 前后缀匹配指针初始为-1边界条件 next[0] -1; // next数组首位固定为-1人为定义的失配边界 // 遍历模式串生成完整的next数组i m 避免数组越界 while(i m) { // 边界情况 或 当前字符匹配成功拓展相等前后缀 if (j -1 || pattern[i] pattern[j]) { i; // 模式串遍历指针后移 j; // 前后缀匹配长度1回退位置后移 next[i] j; // 记录当前位置的失配回退点 } else { j next[j]; // 字符匹配失败j根据next数组向前回退 } } } /** * KMP算法核心匹配函数 * param str 主字符串被查找的长串 * param pattern 模式串要查找的短串 * return 匹配成功返回模式串在主串中首次出现的起始下标 * 匹配失败返回-1 */ int kmp(char* str, char* pattern) { int i 0; // 主串遍历指针从不回溯仅向后移动 int j 0; // 模式串遍历指针失配时根据next回退 int next[100]; // 定义next数组存储模式串失配回退点 getNext(pattern, next); // 预处理模式串生成next数组 int n strlen(str); // 获取主串长度 int m strlen(pattern); // 获取模式串长度 // 主串和模式串均未遍历完时继续匹配 while(i n j m) { // 模式串回退到边界 或 当前主串与模式串字符匹配成功 if (j -1 || str[i] pattern[j]) { i; // 主串指针后移继续匹配下一位 j; // 模式串指针后移继续匹配下一位 } else { j next[j]; // 字符失配主串指针不动模式串指针按next回退 } } // 若模式串指针遍历完所有字符说明完全匹配成功 if (j m) { return i - j; // 计算并返回模式串在主串中的起始下标 } else { return -1; // 匹配失败返回-1 } } // 主函数测试KMP算法匹配效果 int main(int argc, char const *argv[]) { char* str abaabaabacacaabaabcc; // 定义主字符串 char* pattern abaabc; // 定义要查找的模式串 printf(%d\n, kmp(str, pattern)); // 调用KMP函数打印匹配结果 return 0; }4. 算法匹配执行示例以上述测试代码为例主串为abaabaabacacaabaabcc模式串为abaabc经getNext函数预处理后生成的 next 数组为[-1,0,0,1,2,0]。匹配过程中主串指针i始终向后移动当遇到字符失配时模式串指针j根据 next 数组回退到对应位置而非重置为 0最终会在主串下标 5的位置匹配到模式串因此代码运行结果输出5。5. 算法特点优点彻底解决了暴力算法的无效回溯问题主串指针仅遍历一次预处理阶段时间复杂度 O (m)匹配阶段时间复杂度 O (n)整体时间复杂度为 O (nm)n 为主串长度m 为模式串长度在长字符串匹配场景下效率远高于暴力算法。缺点基础版 next 数组存在少量冗余回退可通过优化 next 数组为 nextval 数组解决需要额外的数组空间存储 next 数组空间复杂度为 O (m)属于空间换时间的经典算法设计思路。三、暴力算法与 KMP 算法核心对比对比维度暴力匹配算法BFKMP 算法核心思路逐位匹配失配后主串、模式串指针均回溯预处理模式串生成 next 数组失配仅模式串指针回退主串指针不回溯时间复杂度最坏 O (n*m)最好 O (n)整体 O (nm)无最坏情况效率稳定空间复杂度O (1)无需额外辅助空间O (m)需要存储 next 数组实现难度逻辑简单代码易实现需理解 next 数组原理实现稍复杂适用场景短字符串、简单匹配场景对效率要求不高长字符串、高频匹配场景对效率要求较高四、408真题演练KMP 算法的核心是next 数组失配时通过next数组回退模式串指针j主串指针i保持不变。确定模式串tt abaababc索引从 0 开始索引 j01234567字符 t [j]abaababc计算模式串的next数组next[j]表示t[0..j-1]的最长公共前后缀长度。next[0] -1约定next[1] 0子串a无前后缀next[2] 0子串abnext[3] 1子串aba最长公共前后缀为anext[4] 2子串abaa最长公共前后缀为abnext[5] 2子串abaab最长公共前后缀为abnext[6] 3子串abaaba最长公共前后缀为abanext[7] 4子串abaabab最长公共前后缀为abab完整next数组[-1, 0, 0, 1, 2, 2, 3, 4]失配处理题目中第一次失配时i5, j5根据 KMP 规则主串指针i保持不变即i5模式串指针j回退到next[j] next[5] 2答案C步骤 1计算模式串S的next数组模式串S abaabc索引从 0 开始索引 j012345字符 S [j]abaabcnext[j]定义为子串S[0..j-1]的最长公共前后缀长度约定next[0] -1next[0] -1next[1] 0子串a无前后缀next[2] 0子串abnext[3] 1子串aba最长公共前后缀为anext[4] 2子串abaa最长公共前后缀为abnext[5] 2子串abaab最长公共前后缀为ab最终next数组[-1, 0, 0, 1, 2, 2]步骤 2逐次模拟 KMP 匹配过程主串T abaabaab cababaabc模式串S abaabc初始化i0主串指针、j0模式串指针比较次数count0。第 1~6 次比较T[0]avsS[0]a→ 匹配i1,j1count1T[1]bvsS[1]b→ 匹配i2,j2count2T[2]avsS[2]a→ 匹配i3,j3count3T[3]avsS[3]a→ 匹配i4,j4count4T[4]bvsS[4]b→ 匹配i5,j5count5T[5]avsS[5]c→ 失配count6失配处理j next[5] 2i保持5第 7 次比较T[5]avsS[2]a→ 匹配i6,j3count7第 8~11 次比较T[6]avsS[3]a→ 匹配i7,j4count8T[7]bvsS[4]b→ 匹配i8,j5count9T[8]cvsS[5]c→ 匹配i9,j6count10此时j6等于模式串长度6匹配成功 ✅答案B五、总结字符串模式匹配中暴力算法是最基础的实现方式凭借逻辑简单的优势在短字符串匹配中仍有一定应用而 KMP 算法通过预处理生成 next 数组的巧妙设计用少量的空间开销换来了时间效率的大幅提升解决了暴力算法的无效回溯问题成为长字符串模式匹配的经典算法。理解 KMP 算法的关键在于掌握next 数组的生成原理—— 本质是模式串的自匹配记录每个位置的最长相等前后缀长度这也是 KMP 算法的核心精髓。掌握这两种算法能为后续学习更高效的字符串匹配算法如 BM 算法、Sunday 算法打下坚实的基础。
（支持资料、图片参考_相关定制）_文章底部可以扫码)
