字符串匹配-KMP算法（通俗易懂）
KMP算法学了N次，忘了N次，可能因为每次都没有理解理解透彻，故写下这篇博客，帮助大家更是帮助自己能更好地理解KMP算法的原理
目录
题目背景
暴力求解
KMP优势
next数组的作用
next数组的原理
next数组的建立
题目背景
给定两个字符串A（长度为n），和字符串B（长度为m），返回在A串中，与B串相同的字串的位置。
暴力求解
很容易想到的暴力做法。i指针指向A串的字符，j指针指向B串的字符，然后一位一位比较，每次遇到不匹配的情况，i指针都要回溯，且j指针回到B串开头。时间复杂度是O（n*m）
KMP优势
可以发现，在暴力做法中，i指针回溯后的重新比较花费的大量的时间，那么KMP与之相比的优势就在于i指针不需要进行回溯，只前进不倒退，而j指针也不再每次回到B串开头，从而将复杂度降为线性。O（n+m）
next数组的作用
而KMP实现以上优势最关键的又在于next数组，正是因为他的存在，当遇到无法匹配时，i指针不用回溯，只需要将j指针转到next[j-1]即可。假设我们此时已经拥有了next数组，那么使用next数组进行匹配时的代码如下：
while (i<n){while (j && A[i] != B[j])j = nxt[j-1];if (A[i] == B[j])j++;if (j == m){ans = i - j + 1;j = nxt[j-1];cout<<ans<<endl;}i++;}next数组的原理
接下来我们要理解为什么可以像上述这么做。先来看看next数组的含义，next[j]表示，在B[0]~B[j]所组成的这个子串中最长公共前后缀的长度为x，通俗地说，若next[j]的值为x，则说明这个（B[0]~B[j]所组成的）子串的前x个字符和后x个字符相同。（以上提到的字串均为真字串）
以B串=ABABC为例，此时next[0]~next[4]分别就是0，0，1，2，0。
那么再假设A串=ABABABCAA为例，（下表从0开始）i和j指针从0一直匹配到3都相等，那么此时i和j都等于4，并且发现两者不相等。那么：
- 根据前面的匹配我们知道的，B[j]前面的j-1个字符（ABAB），一定和A[i]前面的j-1个字符相等(ABAB)。所以B[j]前面的next[j-1]个字符(AB)，也一定和A[i]前面的next[j-1]个字符(AB)相等。（因为next[j-1] < j-1）
- 那么再根据next数组的含义我们知道，B[j]前面的next[j-1]个字符(AB)，和B串开头的next[j-1]个字符(AB)相同。
综合1，2我们可得，所以A[i]前面的next[j-1]个字符(AB)，和B串开头的next[j-1]字符(AB)一定相等！
所以就无需重新从头匹配，只需要从B串的第next[j-1]+1个字符开始匹配，即B[next[j-1]]，（数组下标从0开始），故令 j = next[j-1]即可。
重复上述操作，直到B[j]与A[i]相等或者j =0时停止。
next数组的建立
那么最后剩下的问题就是，我们如何建立起这个方便的next数组，也就是如何快速求出B串每一个（真）字串的最长公共前后缀。在这里，我们可以用到递推的方式。
我们利用一个i指针线性遍历每一个字符并求出next[i]。
显然，当i == 0时，next[i] = 0。
当i！=0时，已知next[i-1] = j，所以B[i]前面的j个字符一定与B串开头的j个字符相等。那么再看B串的第j+1个字符，即B[j]与当前B[i]是否相等，若相等，则next[i] = j + 1 = next[i-1] + 1。
若不相等，已知next[i-1] = j，所以
- B[i]前面的j个字符一定与B串开头的j个字符相等
- 假设B串的第j个字符，即B[j-1]，它的next[j-1] = y，，故B[i]前面的y个字符一定与B串开头的y个字符相等（因为y<j）
综合1，2可知，只需要再匹配B[i]和B[y]（即B[next[j-1]）即可，也就是说只要令j = next[j-1]，再比较B[i]和B[j]即可。
重复上述操作，直到字符匹配或者y=0时停止。建立过程代码如下：
while (i<n){j = nxt[i-1];while (j && B[i] != B[j])j = nxt[j-1];if (B[i] == B[j])nxt[i] = j+1;elsenxt[i] = 0;i++;}不明白的同学可以以ABACABAB为例，写一下过程。最后next数组的值分别是0，0，1，0，1，2，3，2
细致的同学已经发现了，建立next数组的过程和使用next数组进行匹配的过程极其相似。那是因为我们可以将建立next数组的过程也视为是一种字符串匹配，只不过匹配的是前缀串和后缀串，每次不匹配时，依旧通过已经建立起的next数组进行跳跃，思想都是一样的。
附上洛谷KMP模板题的完整代码P3375 【模板】KMP字符串匹配 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<bits/stdc++.h>
using namespace std;
char A[1000005],B[1000005];
int nxt[1000005];
int main()
{scanf("%s%s",A,B);int i,j,n,m,ans;i = 0;j = 0;n = strlen(A);m = strlen(B);nxt[0] = 0;i++;while (i<n){j = nxt[i-1];while (j && B[i] != B[j])j = nxt[j-1];if (B[i] == B[j])nxt[i] = j+1;elsenxt[i] = 0;i++;}i = 0;while (i<n){while (j && A[i] != B[j])j = nxt[j-1];if (A[i] == B[j])j++;if (j == m){ans = i - j + 1;j = nxt[j-1];cout<<ans<<endl;}i++;}for (int i=0;i<m;i++)printf("%d ",nxt[i]);return 0;} 希望这篇文章能够帮到你！