字符串匹配是计算机最基础的操作之一——搜索关键词、文本替换、DNA 序列比对。这篇从暴力匹配讲到 KMP再到 BM 和 Sunday 算法。一、暴力匹配publicclassBruteForce{publicstaticintindexOf(Stringtext,Stringpattern){intntext.length();intmpattern.length();for(inti0;in-m;i){intj;for(j0;jm;j){if(text.charAt(ij)!pattern.charAt(j)){break;}}if(jm){returni;// 匹配成功}}return-1;}}时间复杂度O(n × m)空间复杂度O(1)最坏情况举例主串 AAAAAA...AAAAAB 模式串 AAAAB 每一趟都要比到最后才发现不匹配 → 极低效二、KMP 算法1. 核心思想KMP 的核心思想是匹配失败时主串指针不回溯利用已匹配部分的信息将模式串向右滑动尽可能远的距离。主串 ABABABC 模式串 ABABC 匹配到第 5 个字符时失败 A B A B A B C A B A B C ↑ ↑ i4 j4 不匹配 暴力做法i 回退到 1j 回退到 0 KMP 做法i 不动j 跳到 2 因为已匹配的 ABAB 中前缀 AB 后缀 AB2. next 数组next[j] 表示当模式串第 j 个字符匹配失败时j 应该回退到的位置。next[0] -1第一个字符就失败的情况 next[1] 0第二个字符失败回到开头 计算规则 next[j] 模式串 [0:j-1] 中最长相等前后缀的长度3. 手算 next 数组模式串 abaabcac j0next[0] -1 j1T[0:0] → 无子串 → next[1] 0 j2T[0:1]ab → 前缀{a} 后缀{b} → 无相等 → next[2] 0 j3T[0:2]aba → 前缀{a,ab} 后缀{a,ba} → 相等a长度1 → next[3]1 j4T[0:3]abaa → 前缀{a,ab,aba} 后缀{a,aa,baa} → 相等a长度1 → next[4]1 j5T[0:4]abaab → 前缀{a,ab,aba,abaa} 后缀{b,ab,aab,baab} → 相等ab长度2 → next[5]2 j6T[0:5]abaabc → 前缀和后缀 → 无相等 → next[6]0 → 优化后2 j7T[0:6]abaabca → 相等a长度1 → next[7]1 next [-1, 0, 0, 1, 1, 2, 0, 1]4. KMP 匹配代码publicclassKMP{publicstaticint[]getNext(Stringpattern){intmpattern.length();int[]nextnewint[m];next[0]-1;inti0,j-1;while(im-1){if(j-1||pattern.charAt(i)pattern.charAt(j)){i;j;next[i]j;}else{jnext[j];}}returnnext;}publicstaticintindexOf(Stringtext,Stringpattern){intntext.length();intmpattern.length();if(m0)return0;int[]nextgetNext(pattern);inti0,j0;while(injm){if(j-1||text.charAt(i)pattern.charAt(j)){i;j;}else{jnext[j];}}returnjm?i-j:-1;}}5. next 数组的优化——nextval/** * 当 pattern[i] pattern[j] 时 * 即使跳转到 j 也会匹配失败所以继续跳转 */publicstaticint[]getNextVal(Stringpattern){intmpattern.length();int[]nextvalnewint[m];nextval[0]-1;inti0,j-1;while(im-1){if(j-1||pattern.charAt(i)pattern.charAt(j)){i;j;if(pattern.charAt(i)!pattern.charAt(j)){nextval[i]j;}else{nextval[i]nextval[j];}}else{jnextval[j];}}returnnextval;}三、BM 算法BM 算法从模式串的尾部开始匹配利用坏字符规则和好后缀规则。1. 坏字符规则模式串从右向左比较 遇到不匹配的字符坏字符移动模式串使坏字符对齐 例子 主串 EXAMPLE 模式串APPLES ↑ 坏字符E 在模式串中不存在 模式串整体移到 E 后面2. 好后缀规则已匹配的部分称为好后缀 查找好后缀在模式串中是否在其他位置出现 如果出现移动到该位置否则移动到好后缀的前缀位置四、Sunday 算法Sunday 算法是比 BM 更快的一种匹配算法理解起来也更简单。1. 核心思想匹配失败时关注主串中模式串后面一个位置的字符 根据该字符在模式串中的位置决定移动距离 例子 主串 substring searching 模式串search 第一趟匹配 substring searching search ↑i0, j0 匹配 ... ↑i3, j3 不匹配b ≠ a 模式串后面的字符是 t t 在模式串中不存在 → 直接移动 7 位2. Sunday 算法实现publicclassSunday{publicstaticintindexOf(Stringtext,Stringpattern){intntext.length();intmpattern.length();if(m0)return0;// 构建偏移表int[]shiftnewint[256];for(inti0;i256;i){shift[i]m1;// 默认偏移 模式串长度 1}for(inti0;im;i){shift[pattern.charAt(i)]m-i;}inti0;// 主串指针while(in-m){intj0;while(jmtext.charAt(ij)pattern.charAt(j)){j;}if(jm)returni;// 匹配成功// 移动看主串中模式串后的第一个字符if(imn){ishift[text.charAt(im)];}else{break;}}return-1;}}3. Sunday vs KMP vs BM算法平均时间最坏时间预处理实现难度暴力O(nm)O(nm)无⭐KMPO(nm)O(nm)next数组⭐⭐⭐BMO(n/m)O(nm)坏字符好后缀⭐⭐⭐⭐SundayO(n/m)O(nm)偏移表⭐⭐实际使用建议 一般场景 → KMP稳定考研必考 文本搜索 → Sunday代码简单平均快 性能极致 → BM最复杂也最快五、408 考研常见考题题1手算 next 数组模式串 ababa 的 next 数组 j0: next[0] -1 j1: next[1] 0 j2: ab → 无相等 → next[2]0 j3: aba → a长度1 → next[3]1 j4: abab → ab长度2 → next[4]2 next [-1, 0, 0, 1, 2]题2KMP 匹配过程主串 ababcabcacbab模式串 abcac 请用 KMP 算法写出匹配过程 next [-1, 0, 0, 0, 1] 第一趟ababcabcacbab abcac i3失败,j3 → next[3]0 第二趟ababcabcacbab abcac i3失败,j0 → next[0]-1 → i4,j0 第三趟ababcabcacbab abcac i4失败,j0 → next[0]-1 → i5,j0 第四趟ababcabcacbab abcac 匹配成功i9,j5 → 位置9-54题3模式串的优化模式串 aaaaaaab next 数组[-1, 0, 1, 2, 3, 4, 5, 6] nextval 数组[-1, -1, -1, -1, -1, -1, -1, 6] 优化效果 当遇到 b 之前所有字符都是 a 在 a 上匹配失败时跳到任何一个 a 结果都一样 nextval 直接跳到第一个字符减少不必要的比较六、字符串匹配在实际开发中的应用// 1. Java String.indexOf() 使用的就是暴力匹配的优化版StringtextHello World;intindextext.indexOf(World);// 2. 文本编辑器的查找功能// 通常使用 Sunday 或 BM 算法// 3. 入侵检测系统// 使用 AC 自动机Aho-Corasick多模式匹配// 4. DNA 序列比对// 使用 BLAST 等专门算法总结暴力匹配 → O(nm) → 简单但慢 KMP → O(nm) → 考研重点能手算 next 数组 Sunday → O(n/m) → 代码简单实际应用中常用 BM → O(n/m) → 最复杂最快 考研重点手算 next 数组、nextval 优化、KMP 匹配过程 觉得有用的话点赞 关注【张老师技术栈】吧每周更新 Java/Python/爬虫 实战干货不让你白来。