数据结构与算法 ｜ KMP算法及其改进算法的核心思路 （C语言实现）

KMP算法及其实现

kmp算法是子串匹配算法（模式匹配算法）的一种，虽然并不是速度最快的，但是其算法思想非常巧妙。请允许我尝试用白话描述一下其思想，如果有什么不对的地方，恳请矫正。详细的讲解可以看小甲鱼的《数据结构和算法》KMP算法。

1. 假设S为目标串，即母串
2. 假设T为模式串，即子串

一、KMP算法思路

解决子串匹配的问题，暴力算法是最容易想到的，但是效率太低了。暴力算法效率低的原因是：进行了大量的重复操作。
白话：类似于走迷宫，一条路走不通的时候，暴力算法的思路是返回起点，换路重新走。

KMP算法解决了这个缺点：给走迷宫的人，添加了一个“领航员”

具体的做法是：为每个子串元素增加了一个NEXT指针（领航员的标记），用于标记如果子串的某个元素与母串失配时（匹配不成功），进行下一次的配对时可以偷多大的懒。

---

算法核心思想：避免不必要的回溯，那么什么是不必要的呢？这个问题由模式串决定，不是由目标串决定！
白话：我要偷懒！查找子串到底在母串的哪个位置过程中，当匹配过程中发生失配时，尽可能地偷懒，尽可能地少配对元素。而能偷多少懒，取决于子串长什么样，跟母串无关。
举例说明：
假设母串为S="AABCAAAB"，子串T="AAAB"，

其中，i、j分别表示字符串中元素的位置，S[0]和T[0]存放字符串的长度。

NEXT指针：用于指明下一次匹配中，与当前（母串S）失配元素开始匹配的子串T的元素位置。

也可以这么说：
当模式匹配串T失配的时候，NEXT数组对应的元素指导应该用T串的哪个元素进行下一轮的匹配。

当进行第一次匹配时（无法偷懒）：匹配到第三个元素时失配（匹配不成功）S[3]!=T[3]，可以发现前两个元素是匹配成功的！

当进行第二次匹配时（尝试偷懒）：暴力算法时从母串的第二个元素开始匹配。而KMP算法则开始偷懒，因为前两个元素在上一个匹配时，是匹配成功的，可以借鉴过来，不用再重复工作。

KMP算法从“领航员的地图——NEXT指针”发现，第二次匹配时，可以从子串的第2个元素位置开始，将之与母串的失配元素开始匹配。

总之，KMP算法，说白了，就是尝试偷懒！请一个“领航员”NEXT指路！

具体如何偷懒，就不过多描述了，有很多老师解释得很清楚，我在这里只尝试简单解释一下：

在失配时，查找前面匹配成功的子串——“匹配子串”（对于模式串和目标串来说，这个子串是相同的），在该子串中寻找后缀与前缀尽可能多相同的元素。

如在上例第一次匹配中，前面匹配成功的子串是"AA"，前缀"A"等于后缀"A"，因此，第二次查找中，可以跳过第一个元素"A"

而正是因为对于模式串和目标串来说，“匹配子串”是相同的，所以当发生失配时，如何偷懒是取决于模式串长什么样子。

二、改进的KMP算法思路

后来，人们发现KMP算法是有缺陷的，比如上例中，子串T="AAAB"，前三个元素是相同的，T[1]=T[2]=T[3]="A"，当失配发生在前3个元素时，因为知道前3个元素相同，所以完全没有必要再将前3个元素再与母串中的失配元素进行比较。

基于这个思想，我们来看改进的KMP算法将如何工作：在第二次匹配中，直接越过目标串的失配元素S[3]，将模式串与失配元素的下一个元素S[4]进行匹配。

改进的KMP算法的改进之处：如果T[k]==T[k+1]，则NEXT[k+1]=NEXT[k]。

三、C语言实现KMP算法及改进的KMP算法

如果上面的解释还是让你无法理解KMP算法的核心思想（本菜对此感到抱歉T_T），那么还是看代码最直观的吧！

//C语言实现KMP算法及其改进的KMP算法
//下面是KMP算法中获取NEXT指针
void get_next(String T,int *next)  //输入母串，next数组的指针
{
    j=0;  //前缀
	i=1;  //后缀
	next[1]=0;   //思路：当S[1]!=T[1]时跳过目标串的当前失配元素
	
	while(i<T[0])  //循环判断：“匹配子串的后缀不超过子串长度”
	{
		//当j=0时，得到next[2]=1
		if(j==0 || T[i]==T[j])  //当匹配子串中前缀等于后缀T[i]==T[j]
		{
   			i++;  //后缀的下一个元素位置：失配元素的位置
   			j++;  //前缀的下一个元素位置
   			next[i]=j;  //当S[i]!=T[i]时，下次匹配从判断S[i]==T[next[i]]开始
		}
		else
		{
   			//前缀不等于后缀，将j回溯
   			j=next[j];  
		}
	}
}

//改进的方法获取NEXT指针
void get_next1(String T,int *next)
{
	j=0;
	i=1;
	next[1]=0;
	while(i<T[0])
	{
		if(j= =0 || T[i]==T[j])
		{
   			i++;
   			j++;
         	if(T[i]!=T[j])  
         	//如果子串中T[i]=T[j]，那么next等于左边相同元素的next
         	{
            	next[i]=j;
         	}
   			else
         	{
            	next[i]=next[j];
         	}
		}
		else
		{
   			//j回溯
   			j=next[j];
		}
	}
}
//因为前缀是固定的，后缀是相对的


//返回子串T在主串S第pos个字符之后的位置
//若不存在，则返回0
int Index_KMP(String S,Sting T,int pos)
{
   int i=pos;//后缀
   int j=1;  //前缀
   int next[255];  //next数组
   
   get_next(T,next);  
   //get_next1(T,next);
   
   while(i<=S[0] && j<=T[0])
   {
      if(0==j || S[i]==T[j])
      {
         i++;
         j++;
      }
      else
      {
         j=next[j];
      }
   }
   
   if(j>T[0]) //前缀超出子串长度,表明匹配结束
   {
      return i-T[0];  //此时后缀i包含了匹配成功的子串T的长度，i-T[0]实际上是子串匹T在主串S中的起始位置
   }
   else
   {
      return 0;
   }
}