KMP算法学习

代码随想录-B站视频

KMP ：三位学者首字母，用于匹配字符串。

时间消耗：O(m+n)。

文本串：需要在其中查找模式串。

模式串：不匹配时，不会直接从文本串的下一个字符，而是直接跳到当前已经匹配好的串后继续匹配。

前缀表：一个字符串中每个字符的最长相等前后缀。

前缀：包含首字母，不包含尾字母的所有字串。

后缀：包含尾字母，不包含首字母的所有字串。

最长相等前后缀：

例子：aabaaf

a:是前缀没有后缀，0;

a : aa的长度是1；

b:aab长度是0；

a:aaba长度是1；

a:aabaa长度是2；

f:abaaf长度是0。

a至此得到前缀表：[0,1,0,1,2,0]。

过程：当f不匹配时，查找表发现，前一个位置对应的最长相等前后缀是2，这就是不相等了需要继续去匹配的字符串的位置，相等于跳到前缀的后面，这里就是继续去匹配b的意思。

next（prefix）数组：就是前缀表，表示遇见冲突后next数组会告诉我们需要回退到哪里。

（直接用前缀表就可以实现KMP算法，但是有的实现会进行一些转变）实现过程中会将前缀表进行减一或者右移一位，效果都是初始位置变为-1，后面整体右移或者减一，相当于变成[-1,0,1,0,1,2]或者[-1,0,-1,0,1,-1]。就像上面的在f发生冲突看的是前一位的前缀表，因此整体右移可以直接实现当前位置的匹配，减一个也是访问前一个位置的前缀表，然后再找的时候将这个1再加回来。

实现：循环不变量：遇见冲突看前一位。

next数组：

1. 定义函数来求next数组，传入next数组，传入模式串
2. 初始化next数组和函数中各个变量。需要一个指向前缀末尾位的j和指向后缀末尾位置的i，这里的j还代表了包括i在内的最长相等前后缀的长度。j=0；next[0]=0。
3. 处理前后缀不相同的情况。从i开始进入循环遍历到模式串全部长度，i=1开始，因为i不能和j相等。比较当前的j和i，两者不相等时需要回退（不止一步，while），回退到前一位的前缀表对应的位置（相当于匹配时出现了冲突，j=next[j-1]，更仔细地说就是当前已匹配上的字串中（也就是当前已经匹配上的后缀中）可以不用再匹配的长度），回退到0停止( j!=0 and s[i]!=s[j] )。
4. 处理前后缀相同的情况。s[i]=s[j]时相当于匹配上了，j需要加一，相当于匹配上一个。
5. 更新next数组的值。最后更新next[i]=j。