KMP算法最通俗易懂的理解（超详细）-EW帮帮网

前提说明：KMP算法是由串来实现的，通常的串写法有两种

一种是结构体写法一种是数组写法（两种）

//定长顺序存储表示
typedef struct{
	char ch[maxSize+1];	//多出一个‘\0’作为结束标记
	int length;	
}SString;

//变长分配存储表示
typedef struct{
	char *ch;				//指向动态分配存储区首地址的字符指针
	int length;	
}SString;

一.暴力的BF算法

// 暴力匹配
int Index(SString S, SString T) {
    int t = 1 ;
    int j = 1 ;
    while (i<=S.length&&j<=S.length){
        if(S.ch[i]==T.ch[i]){
            ++i;++j;
        }else{
            i=i-j+2;//推导，后记忆 
            j=1;    //指针后退重新匹配
        }
        if(j>=T.length)
            return i-T.length;
        else return 0;//判断
    }
}

对于暴力算法，如果出现不匹配字符，同时回退 i 和 j 的指针，嵌套 for 循环，时间复杂度 O(S.length*T.length)，空间复杂度O(1)。最主要的问题是，如果字符串中重复的字符比较多，该算法就显得很蠢。

比如 txt = "aaacaaab" pat = "aaab"：

二.KMP算法

KMP 算法的不同之处在于，它会花费空间来记录一些信息，在上述情况中就会显得很聪明

KMP 算法永不回退 txt 的指针 i，不走回头路（不会重复扫描 txt），而是借助 dp 数组中储存的信息把 pat 移到正确的位置继续匹配，时间复杂度只需 O(N)，用空间换时间，所以我认为它是一种动态规划算法。

这种思想，在很多算法中有体现，其实我觉得算法的基本思想就那么几种（基本的,就我这种2b也能掌握的），评论区有无大佬解释一下。

要搞定KMP算法，首先我们要理解以下内容：

1.字符串的前缀，后缀，部分匹配值

引用阮一峰的例子

字符串匹配的KMP算法 - 阮一峰的网络日志 (ruanyifeng.com)

部分匹配值= 共有元素长度

那么此时的你一定会手算KMP了，那就是：移动位数=已匹配的字符数-部分匹配值（相同前后缀）

2.算法改进详解

我们知道，已匹配的字符数为（j-1）编号的数组，匹配不到的数组编号为j，同时减的部分匹配值数组编号为（j-1）

所以引入一个数组，即将部分匹配值数组右移一位的数组

移动位数=已匹配的字符数-部分匹配值

引入数组=到前一个串的部分匹配值

移动位数=（j-1）-引入数组

j=j-移动位数 = 引入数组+1

NEXT数组即为引入数组+1

好，现在知道啥是next数组。但是这玩意怎么求呢？

我们是人，一眼看出相同前后缀。电脑不能看出来。

显然要设计一种算法，来求一个字符串的next数组。

哪么就到了本章最难的：get-next函数

3.get-next函数

KMP算法之求next数组代码讲解_哔哩哔哩_bilibili

可以康下这个视频

void getnext(String t,int next[])
{
   int i=1;//不回溯指针，代表比到哪里了
   int j=0;//回溯指针j==0的
   next[1]=0;//初始化
   while(j<t.length)
   {
      if(j == 0 || t.ch[i] == t.ch[j])
/*
这里分开讲
    j==0的意思是回溯指针j==0的，意味着前缀后缀是不相等的，所以进1,next数组为1
（前无相等）
     t.ch[i] == t.ch[j]意思是字符串相等,即前缀串后缀串相对数+1，可以推出next数组加1
（next[++i] = ++j;下面拆开写的）
*/
      {
         ++i;++j;
         next[i] = j;
      }
      else j = next[j];
/*
如果不相等，而前缀后缀相等的部分可以不比较，因为前面推的kmp算法定理，即下一步比较t.ch[next[j]]与字符是否相对。
*/
   }
}

贴个图醒目一些哈哈

4.kmp算法

int Index_KMP( String s, String T, int next[]){
int i=1,j=1;
while(i<=S. length&&j<=T. length) {
if ( j==0 | |S. ch[i]==T. ch[j]) {
++i; ++j; //继续比较后继字符
}
else
j=next[j]; //模式串向右移动
}
if(j>T. length)
return i-T. length; //匹配成功
else
return 0;
)

这个不加解释，弄得懂getnext函数自然懂

5.小结

关于指针回溯求next的理解
每次求next【i】，可看作前缀与后缀的一次匹配，在该过程中就可以用上之前所求的next，若匹配失败，则像模式串与父串匹配一样，将指针移到next【j-1】上。
求next过程实际上是dp（动态规划），只与前一个状态有关：
若不匹配，一直往前退到0或匹配为止
若匹配，则将之前的结果传递：
因为之前的结果不为0时，前后缀有相等的部分，所以j所指的实际是与当前值相等的前缀，可视为将前缀从前面拖了过来，就不必将指针从前缀开始匹配了，所以之前的结果是可以传递的。

KMP算法最通俗易懂的理解（超详细）