KMP算法个人认为比较抽象，一开始认为很难，但后来通过看题解，上网找资源，终于把KMP算法搞明白了

一.KMP算法的基本概念(来自第一篇题解)

1.s[]是模式串，即比较长的字符串
2.p[]是模板串，即比较短的字符串
3.KMP是一个字符串匹配算法，KMP是取三个人名字的首字母命名的
4.非平凡前缀：指除了最后一个字符以外，一个字符串的全部头部组合
5.非平凡后缀：指除了第一个字符以外，一个字符串的全部尾部组合。
6.部分匹配值：前缀和后缀的最长共有元素的长度。
7.next[]是 “部分匹配值表” ，即next数组，它存储的是每一个下标对应的“部分匹配值”，是KMP算法的核心。

二.暴力做法

最容易的还是想到暴力
一个字一个字的与字串进行比对，一旦匹配失败，就重新跳回主串的下一个字符重新进行匹配
这个暴力算法做了很多无用功，复杂度为 $O(n*m)$

int s[N],p[M];
for(int i=1;i<=n;i++){
    bool flag=true;
    for(int j=1;j<=m;j++){
        if(s[i]!=p[j]){
            flag=false;
            break;
        }
    }
}

模板题

三.样例模拟

有一个长的字符串 $S$ ，和一个短的字符串 $P$ ，如果短的字符串 $P$ 在长的字符串 $S$ 中出现过，输出第一次出现的位置，否则输出 $-1$ 。
例 $1$：长的字符串 $S$ 为 abcuhdafgj ，短字符串 $P$ 为 abcuhd 可以看出从前往后查找，$S$ 的前 $6$ 个字符为 abcuhd ， $P$ 也是abcuhd,于是下标为 $1$ ~ $6$ 输出 $1$

例 $2$：$S$ 为dtgwjdgwj，$P$ 为djshk，从前往后找，一直没有找到，输出 $-1$

四.KMP算法基本思想

KMP算法的基本思路为：当我们发现某一个字符不匹配时，由于已经知道以前遍历过的字符，如何避免“后退”的步骤呢？
假定一个指针，我们不应让他递减，只会向前移动，就会改为线性复杂度
先一个一个的进行匹配，发现某个字符不相等，这时，我们便知道前面读入了哪些字符，便可以跳过这些字符
问：如何知道跳过多少字符？用到KMP中的next[]数组
每次KMP在匹配失败的时候，会去看最后一个匹配的字符它所对应的next[]数值
这个next[]数值代表要跳过多少字符

五.next[]数组的生成

问题：为啥最后一个匹配成功的字符的next[]数值代表了可以跳过多少个字符？
因为之前我们匹配成功的最后两个字符，和跳过的字符是一样的
next[]数组的本质：就是寻找字串中相同前后缀的长度，并且一定是最长的前后缀
例：
字串为ABABC，$A$ 没有和他一样的前后缀，next[]数组为 $0$，$B$ 也没有和他一样的前后缀，next[]数组为 $0$ ，$A$ 和第一个 $A$ 一样，一个前后缀，next[]数组为 $1$
前两个字符是AB,后两个也是AB，长度为 $2$ ，next[]数组为 $2$,最后一个 $C$ 没有和他一样的前后缀字符，于是next[]数组为 $0$。