一.什么是KMP算法
KMP算法，又称模式匹配法，能够在线性时间内判定字符串A[1 ~ N]是否为B[1 ~ M]的子串，并求出字符串A在字符串B中各次出现的位置和出现次数。
二.KMP算法流程(参考算阶)
1.对字符串A进行自我"匹配"。求出一个数组next,其中next[i]表示"A中以i结尾的非前缀子串"与"A的前缀"能够匹配的最长长度,及:
next[i]=max{next[j]},其中 j < i 且 A[1 ~ j]=A[i-j+1 ~ i]。
特别的，当不存在这样的j时，令 next[i]=0。
2.对字符串A与B进行匹配。求出一个数组f,其中**f[i]表示"B中以i结尾的子串(这里可以是前缀)“与"A的前缀”**能够匹配的最长长度，即:
f[i]=max(j),其中 j <= i 且 A[1 ~ j]=B[i-j+1 ~ i]。那么如果f[i]=A.size()则说明A串作为B串中以i为结尾的子串出现了。
三.计算next数组
根据定义，我们知:next[1]=0（没有以A[1]为结尾的非前缀字串）。我们也知道**"A中以i结尾的非前缀子串"与"A的前缀"能够匹配的长度不一定只有一个，而next[i]只是取了最大的那个**。所以我们称所有满足上述条件的j为next[i]的"候选项"。
那么我们求next[i],实际上是枚举next[i-1]的所有"候选项" j，看看A[j+1]与A[i]是否相等，如果相等，那么next[i]=max(next[i],j+1)。如果每个j都不成立的话，那么比较A[i]和A[1] 是否相等即可。这样的正确性在于两个字符串A[i-j+1 ~ i] 和 A[1 ~ j]相等的前提是 A[i-j+1 ~ i-1] 和 A[1 ~ j-1]相等。知道了这些，那么我们只需要快速求出next[i-1]的所有"候选项"即可。问题来了:怎样快速求出next[i-1]的"候选项"?
引理: 若 j 是 next[i] 的一个候选项,即 j<i 且 A[i-j+1 ~ i]=A[1 ~ j],则小于 j 的最大的next[i]的候选项是next[j].换言之,next[j]+1 ~ j-1之间的数都不是next[i]的"候选项"。
证明（介绍两种证法）:
反证法 first.(算阶版) 假设存在 next[j] < k <j 且 k也为 next[i]的"候选项",那么可知A[1 ~ k]=A[i-k+1 ~ i]。如下图:
很明显可知串①等于串②等于串③,则在字符串A[1 ~ j],存在一个长度大于next[j]的非前缀合法串，这与next数组的定义相悖，故不存在这样的情况，即k不存在。则 next[j]即为小于j的最大next[i]的候选项(通过等量相等可知next[j]一定是next[i]的"候选项"。)。
概念法 second.(自己想的)现在我们已知next[i]=j,因为next[i]是next[i]的最大"候选项",即以i为结尾向左延伸合法的最长字符串的长度，则next[i]的下一个"候选项"一定小于next[i],即向左延伸的长度小于next[i],设next[i]=j,next[i]的下一个"候选项"为k,则通过等值代换可知:k一定是next[j]的候选项,我们要求是大小仅次于j候选项，那么k一定等于next[j]了。(这样才能保证k的大小仅次于j，因为next[j]是next[j]最大的候选项),以此类推。。
知道了这些，那么 next[i]的所有"候选项" 及可表示为next[i],next[next[i]],next[next[next[i]]]…,那我们就可以快速的求出next[i]的所有候选项了。
四.代码实现（内含对代码的理解）:
一.next数组的求法
1.初始化 next[1]=j=0,假设next[1 ~ i-1]已求出，下面求解next[i].
2. 不断尝试拓展匹配长度j,如果拓展失败(下一个字符不相等),令j变为next[j],直至j为0(应该重新从头开始匹配)。
3. 如果能拓展成功，匹配长度j就增加1,next[i]的值就是j.
nxt[1]=0;//next是关键字
for(int i=2;j=0/*j总代表next[i-1]*/;i<=n;i++){
while(j>0 && a[i]!=a[j+1]/*匹配不上*/) j=nxt[j];//换为下一个候选项
if(a[i]==a[j+1]) j++;//两种方式结束:j=0 或者a[i]!=a[j+1]。j=0结束后从头开始匹配
nxt[i]=j;
}
二.f数组的求法(与next基本一致)
for(int i=1/*这里从1开始，因为f[1]不一定等于0，需要进行匹配*/,j=0/*j总代表f[i-1]*/;i<=m;i++){
while(j>0 && (j==n/*跳过已经完全匹配的候选项*/ || b[i]!=a[j+1])) j=nxt[j];//解释一下:这里j=nxt[j]的原因与上边相似:b[i-j+1 ~ i]= a[1 ~ j]。要求下一个b的后缀能匹配a的前缀的最大长度，相当于是在a[1 ~ j]里求以j结尾的非前缀后缀与前缀的最大匹配长度，即nxt[j]。
if(b[i]==a[j+1]) j++;
f[i]=j;
// if(f[i]==n) 此时就是 A在B 中的某一次出现.
}
