在日常开发中，字符串匹配是最常见的操作之一。比如：在文本中搜索关键词、在 DNA 序列中查找特定片段、在编辑器中使用 Ctrl+F 查找。KMP 算法（Knuth-Morris-Pratt）是一种高效的字符串匹配算法，它的核心思想是：当匹配失败时，利用已匹配的信息跳过不必要的比较。1. 什么是字符串匹配？1.1 问题定义给定一个文本串text和一个模式串pattern，找出pattern在text中第一次出现的位置。示例：text ="ABABDABACDABABCABAB"pattern ="ABABCABAB"结果：位置 9（从 0 开始计数）1.2 暴力匹配（BF 算法）最直观的方法是暴力匹配：逐个字符比较，失败就回退。intbruteForce(conststringtext,conststringpattern){intn=text.size();intm=pattern.size();for(inti=0;i=n-m;i++){intj=0;while(jmtext[i+j]==pattern[j]){j++;}if(j==m){returni;// 找到匹配}}return-1;// 未找到}问题：时间复杂度为 O(n × m)，当文本很长时效率极低。1.3 暴力匹配的问题文本：A B A B A B C 模式：A B A B C ✓ ✓ ✓ ✓ ✗匹配到第 5 个字符时失败，暴力算法会回退到文本的第 2 个字符重新开始：文本：A B A B A B C 模式： A B A B C ✗但其实我们已经知道前 4 个字符是ABAB，完全可以利用这个信息跳过一些不必要的比较。2. KMP 算法的核心思想2.1 关键观察KMP 的核心思想是：当匹配失败时，模式串不需要回退到开头，而是根据已匹配的部分跳到合适的位置继续匹配。文本：A B A B A B C 模式：A B A B C ↑ 失败点 已知：模式串前 4 个字符是 ABAB 问题：ABAB 的哪个后缀等于它的前缀？ 答案：AB（长度为 2） 所以：模式串可以直接跳到位置 2 继续匹配2.2 next 数组（部分匹配表）为了实现这个跳转，KMP 算法预处理模式串，计算一个next 数组（也叫部分匹配表 PMT）。next[j]的含义：模式串中，以j结尾的子串的最长相等前后缀长度。示例：模式串ABABCABABj子串最长相等前后缀next[j]0A无01AB无02ABAA13ABABAB24ABABC无05ABABCAA16ABABCABAB27ABABCABAABA38ABABCABABABAB42.3 如何使用 next 数组当text[i]和pattern[j]不匹配时：如果j 0，将j跳转到next[j-1]如果j == 0，只移动文本指针iintkmpSearch(conststringtext,conststringpattern){intn=text.size();intm=pattern.size();if(m==0)return0;// 计算 next 数组vectorintnext=computeNext(pattern);inti=0;// 文本指针intj=0;// 模式指针while(in){if(text[i]==pattern[j]){i++;j++;if(j==m){returni-j;// 找到匹配}}elseif(j0){j=next[j-1];// 跳转}else{i
【算法】小白也能懂 · 第 17 节：KMP 字符串匹配算法
发布时间：2026/5/28 22:46:17
在日常开发中，字符串匹配是最常见的操作之一。比如：在文本中搜索关键词、在 DNA 序列中查找特定片段、在编辑器中使用 Ctrl+F 查找。KMP 算法（Knuth-Morris-Pratt）是一种高效的字符串匹配算法，它的核心思想是：当匹配失败时，利用已匹配的信息跳过不必要的比较。1. 什么是字符串匹配？1.1 问题定义给定一个文本串text和一个模式串pattern，找出pattern在text中第一次出现的位置。示例：text ="ABABDABACDABABCABAB"pattern ="ABABCABAB"结果：位置 9（从 0 开始计数）1.2 暴力匹配（BF 算法）最直观的方法是暴力匹配：逐个字符比较，失败就回退。intbruteForce(conststringtext,conststringpattern){intn=text.size();intm=pattern.size();for(inti=0;i=n-m;i++){intj=0;while(jmtext[i+j]==pattern[j]){j++;}if(j==m){returni;// 找到匹配}}return-1;// 未找到}问题：时间复杂度为 O(n × m)，当文本很长时效率极低。1.3 暴力匹配的问题文本：A B A B A B C 模式：A B A B C ✓ ✓ ✓ ✓ ✗匹配到第 5 个字符时失败，暴力算法会回退到文本的第 2 个字符重新开始：文本：A B A B A B C 模式： A B A B C ✗但其实我们已经知道前 4 个字符是ABAB，完全可以利用这个信息跳过一些不必要的比较。2. KMP 算法的核心思想2.1 关键观察KMP 的核心思想是：当匹配失败时，模式串不需要回退到开头，而是根据已匹配的部分跳到合适的位置继续匹配。文本：A B A B A B C 模式：A B A B C ↑ 失败点 已知：模式串前 4 个字符是 ABAB 问题：ABAB 的哪个后缀等于它的前缀？ 答案：AB（长度为 2） 所以：模式串可以直接跳到位置 2 继续匹配2.2 next 数组（部分匹配表）为了实现这个跳转，KMP 算法预处理模式串，计算一个next 数组（也叫部分匹配表 PMT）。next[j]的含义：模式串中，以j结尾的子串的最长相等前后缀长度。示例：模式串ABABCABABj子串最长相等前后缀next[j]0A无01AB无02ABAA13ABABAB24ABABC无05ABABCAA16ABABCABAB27ABABCABAABA38ABABCABABABAB42.3 如何使用 next 数组当text[i]和pattern[j]不匹配时：如果j 0，将j跳转到next[j-1]如果j == 0，只移动文本指针iintkmpSearch(conststringtext,conststringpattern){intn=text.size();intm=pattern.size();if(m==0)return0;// 计算 next 数组vectorintnext=computeNext(pattern);inti=0;// 文本指针intj=0;// 模式指针while(in){if(text[i]==pattern[j]){i++;j++;if(j==m){returni-j;// 找到匹配}}elseif(j0){j=next[j-1];// 跳转}else{i
