【算法】小白也能懂 · 第 17 节：KMP 字符串匹配算法

在日常开发中，字符串匹配是最常见的操作之一。比如：在文本中搜索关键词、在 DNA 序列中查找特定片段、在编辑器中使用 Ctrl+F 查找。

KMP 算法（Knuth-Morris-Pratt）是一种高效的字符串匹配算法，它的核心思想是：当匹配失败时，利用已匹配的信息跳过不必要的比较。

1. 什么是字符串匹配？

1.1 问题定义

给定一个文本串text和一个模式串pattern，找出pattern在text中第一次出现的位置。

示例：

• text ="ABABDABACDABABCABAB"
• pattern ="ABABCABAB"
• 结果：位置 9（从 0 开始计数）

1.2 暴力匹配（BF 算法）

最直观的方法是暴力匹配：逐个字符比较，失败就回退。

intbruteForce(conststring&text,conststring&pattern){intn=text.size();intm=pattern.size();for(inti=0;i<=n-m;i++){intj=0;while(j<m&&text[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结尾的子串的最长相等前后缀长度。

示例：模式串ABABCABAB

2.3 如何使用 next 数组

当text[i]和pattern[j]不匹配时：

• 如果j > 0，将j跳转到next[j-1]
• 如果j == 0，只移动文本指针i

intkmpSearch(conststring&text,conststring&pattern){intn=text.size();intm=pattern.size();if(m==0)return0;// 计算 next 数组vector<int>next=computeNext(pattern);inti=0;// 文本指针intj=0;// 模式指针while(i<n){if(text[i]==pattern[j]){i++;j++;if(j==m){returni-j;// 找到匹配}}elseif(j>0){j=next[j-1];// 跳转}else{i