KMP算法

强烈推荐Carl老哥的视频！！！

多看几遍肯定是可以学会的。

理论篇——帮你把KMP算法学个通透！（理论篇）_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili

求Next数组代码篇——帮你把KMP算法学个通透！（求next数组代码篇）_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili

1.什么是KMP算法

​ KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。(百度百科)

2.KMP算法能解决哪些问题

解决字符串匹配问题

给出文本串和模式串，用两层for循环进行匹配，进行暴力匹配，时间复杂度是O(m,n).其中m是模式串长度，n是文本串长度。

3.KMP算法是如何运行的

给出两个要匹配的串，文本串和模式串。

在这里插入图片描述

第一次匹配

在这里插入图片描述

第二次匹配

在这里插入图片描述

跳到b处继续进行匹配。

这就是KMP算法。

4.KMP算法是如何进行跳的

用到了很重要的表——前缀表。

那么，KMP算法为什么不用hash表或者其它表呢?

前缀表的特性：

• 如何实现：当进行到不匹配的元素时，找到该元素前面的字串，找到一组相等的前后缀，在该前缀的后面进行第二次匹配，就跳过去了。其实就是找最长相等前后缀的长度，从这个以这个长度为下标的元素开始进行匹配。
• 前缀：包括首元素不包括尾元素的所有字串，都称为前缀。
• 后缀：包括尾元素不包括首元素的所有字串，都称为后缀。

5.如何求取前缀表

• 求最长相等(公共)前后缀
  • a的最长相等(公共)前后缀是0 aa的最长相等(公共)前后缀是1 aab的最长相等(公共)前后缀是0

  ​ aaba的最长相等(公共)前后缀是1 ​ aabaa的最长相等(公共)前后缀是2 ​ aabaaf的最长相等(公共)前后缀是0 ​ 所以得出此模式串的前缀表是010120

• 得到最长相等(公共)前后缀是2
  • 2意味着：这里有一个后缀aa,前面有一个与其相等的前缀aa。
  • 在后缀(aa)的后面(是f)后面不匹配(冲突)了。
  • 就找与其相等的前缀(前面那个aa)后面那个元素(b)开始匹配。
  • (其实就是从最长相等前后缀的长度下标开始。)
  • (此模式串最长相等前后缀是2，就从该模式串下标为2的元素开始匹配。)
  • (2表示的是最长相等前后缀的长度，我们要跳到前缀的后面，前缀的后面的下标正好是前缀的长度，因为串的下标是从0开始的。)
• 匹配成功,完成匹配过程。

流程图:

在这里插入图片描述

6.KMP算法的实现

有的做法会将前缀表进行一些调整，但总的思想是相同的。

有的用next数组，有的用perfix，这里用的Next数组。

碰到了冲突的位置，我们要向前回退，这是Next数组的核心所在。

对于实现，不同的人有不同的方法。

这里就用前缀表作为我们的Next数组。

求出来的Next数组就是该模式串的前缀表。

那么具体的代码应该怎么写呢？

明确求Next数组有几个步骤 1.初始化 2.处理前后缀不同的情况 3.处理前后缀不相同的情况 4.更新Next数组的值

j指向前缀末尾位置(还代表着i之前包括i,字串的最长相等前后缀的长度)。

i指向后缀末尾位置。

void getNext(int* next,const string&S)//S为模式串，（此代码类似于伪代码）
{ 
    //1.初始化
   	int j = 0;//j初始化为0，前缀一开始是从开始的位置开始。
    next[0];//next数组初始位置也是0。
    //初始化完成
    //i的初始化就进入到我们的循环遍历里了
    //因为要比较前后缀所对应的字符是否相等，那i就应该是从1开始，这样i和j才能进行比较
    for(int i = 1;i<S.size;i++)
    {
        //2.处理前后缀不相同情况
        //遇到不匹配看前一位 
        //这里的while容易写成if，我们回退的过程并不是一步就完事的
        //要判断前一位所以j>0 
        //否则产生负数会造成数组越界
        while(j > 0 && S[i] != S[j])
        {
            j = next[j-1];
        }
        //3.处理前后缀相同的情况
        //这时候j应该+1，因为j不仅代表着前缀末尾的位置，还代表着i以及i之前这个字串的最长相等前后缀的长度。
        if(S[i] == S[j])
        {
            j++;        
        }
        //更新Next数组
        next[i] = j;
        //在循环里面,i++，向后面走一位
	}
}