KMP之前缀表原理详解（Day 6）

KMP之前缀表原理详解（Day 6）

文章目录

• 首先明确一下前缀、后缀和前缀表的概念：
• 接下来有两种情况要处理：1. str[i] == str[j]；2. str[i] != str[j]；
• 我们就这种情况来讨论一下之前的问题：为什么要回退？回退到哪里？
• • 1.如果不按上述回退，应该怎么比？
  • 2.为什么回退就不重复比较了呢？
  • 3.为什么回退到前一位的next数组值的下标刚刚好就可以？
• 理论讲完了，我们来写一下代码：

用KMP算法的前提是要有前缀表，那么如何计算前缀表呢？我们以字符串 str = “aaabbaaaa"为例。

首先明确一下前缀、后缀和前缀表的概念：

前缀：必须包含第一个字母但不包含最后一个字母的连续子串
后缀：必须包含最后一个字母但不包含第一个字母的连续子串
前缀表：最长相等前后缀（即这个字符串的前缀和后缀相等，还是最长的那个）
（为了相同的字母区别开来是第几个，采用不同的颜色表示）

这是我们用眼瞅出来的，代码怎么写呢？
首先我这里定义 i 为前缀末尾，j 为后缀末尾（个人习惯 i 在前，但我可能和大部分是反着定义的，但是这不重要）
定义一个next数组用来记录前缀表，初始化为0；
由于前一个str[0]必然无前缀后缀，所以next[0]必然为0，已在初始化时初始好了，所以我们直接从前两个开始

接下来有两种情况要处理：1. str[i] == str[j]；2. str[i] != str[j]；

1. 当 str[i] == str[j] 时，说明前缀末尾和后缀末尾相同，则前缀和后缀相同，由于 i 是指向前缀末尾，所以 i 所代表的下标+1（因为下标从0开始，而个数从1开始）就是此时前缀的长度，即此时最长相等前后缀的长度，而 j 是后缀末尾，j+1则代表了此时取的是前几个
   因为next数组的下标和str的下标是一一对应的，所以next[j] 就是我们要记录的地方
   
   再i++；j++；
   
2. 当 str[i] != str[j] 时，我们要让 i 回退
   这是最让人困惑的地方，为什么要回退？回退到哪里？
   回退是为了避免重复比较，回退到不匹配时 i 所指向的前一个地方的next数组里存的地方
   具体解释将在下面的例子里提到
   
   再次将回退后的i所指向的str[i]和str[j]比较，若依然不相等，继续回退，直到回退到相等或者回退到开头0结束，由于此处是一个不断判断直到找到的过程，所以要用while而不是 if
   若回退后相等了，则更新next数组值，i 和 j 再向后移动一位
   若回退到0依然不想等，则next数组值为0，j向后移动一位，i不动。
   按上述过程，我们之后会遇到这种情况：
   

我们就这种情况来讨论一下之前的问题：为什么要回退？回退到哪里？

1.如果不按上述回退，应该怎么比？

首先明确一下，上图情况是在i从0，j从5开始一直向后匹配出现的不相等的情况，即下标所指处：0和5处相等，1和6处相等，2和7处相等，但3和8处不相等
既然是i从0，j从5开始，那么下一次比较就应该是i从0，j从6开始，匹配结束后next[8]=3，这就是在重复比较

2.为什么回退就不重复比较了呢？

i的前一位的next数组值记录了此时子串的最长相等前后缀：
先看紫色的，再看黄色的，再看绿色的，再看红色的（文字的局限型（）

先看紫色的，再看黄色的，再看绿色的，再看红色的（文字的局限型（）
同样实现了，相当于上面i从0，j从6的匹配过程，但是前两个已经知道匹配结果是相等了，就不用重复匹配了

3.为什么回退到前一位的next数组值的下标刚刚好就可以？

因为前一位的next数组值记录了该子串的最长相等前后缀，那么我们只需要从最长相等的前缀的下一位开始进行比较就可以（结合上图来理解），而由于数组的下标从0开始，个数从1开始，所以next数组所记录的个数刚好就是最长前缀下一位的下标

理论讲完了，我们来写一下代码：

#include<iostream>
#include<string>
using namespace std;int main()
{string s = "aaabbaaaa";int next[9] = { 0 };for (int i = 0, j = 1;j < s.size();j++){while (i > 0 && s[i] != s[j])//大于0是回退到开头就不用在回退了{i = next[i - 1];}if (s[i] == s[j]){i++;next[j] = i;//这里与在理论时我说的是先更新next数组值，即先：next[j] = i+1;//然后：i++;//其中j++写在for循环表达式里了//是一样的}}for (const auto& it : next)cout << it << ' ';//打印出来看一下嘿嘿
}

以上，希望对你有所帮助，KMP真是头疼啊（）

更新：有个小问题，代码那

if (s[i] == s[j])
{i++;next[j] = i; //如果是这样把这个句放在if语句里，那么只有相等的时候才会更新next数组//那不相等的时候next数组就没更新，直接被跳过去了，但是由于初始化全是0，所以被跳过去也依然正确，因为本来就该是0//所以换成先更新next数组再i++的写法也不会出问题，都是初始化为0的功劳
}

if (s[i] == s[j])
{i++;
}
next[j] = i;//如果把这句拿出来，就是不管初始化成什么也不会出错，当然第一个必须初始化为0//因为如果i回退到0了还不相等，i就等于0，没有++，所以next的更新完全正确//所以以这个为标准好一点//但是拿出来就不能先更新next数组值再i++了//所以还是先i++比较好