如何理解KMP算法？

---

KMP算法解决的是什么问题？

在主串 s 中寻找模式串 p 第一次出现的位置。

KMP算法比暴力查找算法好在哪里？

字符串匹配失败时，不让主串指针回退，而是利用已经匹配成功的部分，判断模式串应该往后移动多少。

时间复杂度从 $O(n\times m)$ 减到 $O(n+m)$

---

我在最初学习 KMP 算法时，即使看了很多次 KMP 算法的代码，听了不同的介绍 KMP 算法的视频，也依然对这个算法“为什么这样写”一知半解。今天再一次回看 KMP 算法的代码时，突然茅塞顿开，想写下来自己的理解和大家分享一下。

在看完这则文章后，希望你能对这两个问题理解透彻——为什么创建的 next 数组是模式串指针回退的依据？为什么主串指针不用回退、仅需要模式串回退？

---

BF算法 VS KMP算法

主串 S：  a b a b a b c
模式 P：  a b a b c

S：a b a b a b c
P：a b a b c
		   ↑
发现 b 和 c 不匹配

• 如果是 BF 算法，那么下一步就会是：

    	 ↓(从第二个字符开始)
  S：a b a b a b c
    P：a b a b c
  	 ↑(从头开始)
  

  这其实浪费了很多已知信息。

• 如果是 KMP 算法，那么下一步就会是：

  		   ↓
  S: a b a b a b c
  P:     a b a b c
             ↑
  

---

如何理解 next 数组？

next 数组中存放的是模式串每个子串对应的“最长相等前后缀”。它记录当模式串第 j 个位置匹配失败时，模式串应该跳到哪里继续匹配。

• 什么叫“最长相等前后缀”？

  abab
  前缀：a  ab  aba
  后缀：b  ab  bab
  其中，ab既是前缀又是后缀，所以abab的最长相等前后缀长度是：2
  

• 手算一个 next 数组，理解一下每个元素都代表什么

  下标： 0 1 2 3 4
  字符： a b a b c
  
  next： 0 0 1 2 0
  有时我们让 next[0]=-1，这只是一个规则，是-1是0都可以
  

---

为什么 next 数组是模式串指针回退的依据？

相信在你看 KMP 算法的代码的时候，你会看到这一段：

else {
		j = next[j];
}

如果让 AI 给你解释，它大概只会说“失配时，j 回退到 next[j]”，也就是重复这个算法的“结果”。这也是我一开始一知半解的缘故。

我们不止想知其然，更想知其所以然：凭什么回退到那个地方？

还是用最初的例子：

S：a b a b a b c
P：a b a b c
		   ↑
发现 b 和 c 不匹配

接下来：c的下标是4，对应的next[4]为2，故j变为2，但i仍是4 -> 继续匹配
		   ↓
S: a b a b a b c
P:     a b a b c
           ↑

首先，你还记得 next 数组的元素代表什么吗？没错，是“最长相等前后缀”。next[4] 为 2 ，说明 c 之前的模式串子串的前两个字符和倒数两个字符一一对应相等，也可以理解成“主串的第3个字符和模式串的第1个字符相同，主串的第4个字符和模式串的第2个字符相同”——这句话就是“已知信息”。接下来再比较，就无需关心模式串的前两个字符了，因为主串指针的前两个字符已经和它们匹配了。这也回答了为什么主串指针不需动、仅模式串指针移动。

---

完整的 KMP 算法

#include <stdio.h>
#include <string.h>

// 1.构建next数组
// 遍历模式串，获取每个字符前面大的内容，根据前、后缀相同的最大长度填写对应next中的值
// 例：模式串 abaabc  next数组 -1,0,0,1,1,2
void getNext(char* pattern,int* next，int m) {
		int j=0; // j是后缀指针（也是当前正在计算 next 值的下标的前一个）
		int k=-1; // k是前缀指针，同时也代表当前最长公共前后缀的长度
		
		next[0]=-1; // 固定规则
		
		while(j<m-1) {
				if(k==-1 || pattern[j]==pattern[k]) {
						j++;
						k++;
						next[j]=k;
				}
				else {
						k=next[k];
				}
		}
}

// 2. KMP 匹配主体
int strMatchKMP(char* str, char* pattern) {
    int n=strlen(str);
    int m=strlen(pattern);
    
    if(m==0) return 0; // 模式串为空，默认匹配位置在0
    
    int next[m];
    getNext(pattern,next,m);
    
    int i=0; // 主串指针
    int j=0; // 模式串指针
    
    while(i<n && j<m) {
		    if(j==-1 || str[i]==pattern[j]) {
				    i++;
				    j++;
				}
				else {
						j=next[j]; // 失配（KMP核心）
				}
		}
		
		if(j==m) return i-m;
		else return -1;
}

---

next 数组的构造在这里不再赘述，网上已经有很多清晰的讲解。在看完这篇文章之后，去亲自动手写一遍 KMP 算法的代码吧！
感谢您看到最后，欢迎您的批评指正或者完善补充🌹