KMP学习困惑点，自学自闭自问自答

这两天在看KMP算法，也搜了各种解释和博客、视频来看。
发现似乎大家的实现方式都不太一样，而且大多没讲到关键点上。
（我现在还不是很懂啊哈哈哈哈哈哈哈哈哈尬笑）
【经典算法】——KMP，深入讲解next数组的求解

先来看道题

HDOJ Problem-1686
求文本T中单词W的出现次数

AC代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
char w[10005],t[1000005];
int nex[10005];
void getnext(char *B,int n)
{
	nex[0]=0;
	for(int i=1,j=0;i<n;i++)/* n为B串长度 */
	{
//		j=nex[i-1];j为待计算位前一位对应的最大公共串的下一位(或前一位对应的最大公共串长度)
		while(B[j]!=B[i]&&j>0)//若匹配不上,尝试缩小公共子串,因为B串i之前的j个字符(B[i-j]~B[i-1])与开头的j个(B[0]~B[j-1])相同,直接在前面j个字符里找
			j=nex[j-1];//找最大公共子串的下一位与B[i]相同的最大公共子串,不能用j--,保证B[0]到B[i-1]这段目前匹配前缀后缀始终相同
		if(B[j]==B[i])//公共串下一位字符相同，公共最大长+1
			j++;
		nex[i]=j;//j为0~i最大公共串长度,若最终B[j]!=B[i],j=0
	}
}
int kmp(int m,int n)//m为A串长度,n为B串长度
{
	int ans=0,cmp=0;
	for(int i=0;i<m;i++){
		while(cmp>0&&t[i]!=w[cmp])//第cmp个位置匹配失败
			cmp=nex[cmp-1];//下一轮从匹配成功串的最大公共串的下一位开始匹配
		if(t[i]==w[cmp])//当前字符匹配成功,继续下一位
			cmp++;
		if(cmp==n){//子串匹配成功
			ans++;
			cmp=nex[cmp-1];//本题母串分割各部分间可以有公共部分
		}
	}
	return ans;
}
int main()
{
	int n;
	cin>>n;
	getchar();
	while(n--){
		gets(w);
		gets(t);
		getnext(w,strlen(w));
		printf("%d\n",kmp(strlen(t),strlen(w)));
	}
	return 0;
}

求next数组的疑点解释

一个难点就是求next数组

void getnext(char *B,int n)
{
	nex[0]=0;
	for(int i=1,j=0;i<n;i++)/* n为B串长度 */
	{
//		j=nex[i-1];j为待计算位前一位对应的最大公共串的下一位(或前一位对应的最大公共串长度)
		while(B[j]!=B[i]&&j>0)//若匹配不上,尝试缩小公共子串,因为B串i之前的j个字符(B[i-j]~B[i-1])与开头的j个(B[0]~B[j-1])相同,直接在前面j个字符里找
			j=nex[j-1];//找最大公共子串的下一位与B[i]相同的最大公共子串,不能用j--,保证B[0]到B[i-1]这段目前匹配前缀后缀始终相同
		if(B[j]==B[i])//公共串下一位字符相同，公共最大长+1
			j++;
		nex[i]=j;//j为0~i最大公共串长度,若最终B[j]!=B[i],j=0
	}
}

next数组存储的数值为截止到该下标的子串的最大公共子串的长度，因为字符串从0开始，该数值也为该子串最大公共子串的前缀部分的下一个字符对应的下标。
用递推的方法来求str对应的next数组，求next[i]时，next[0]~next[i-1]都已经求出，令j为next[i-1]即str[i-1]对应的最大公共串的下一位。
注意：i之前的j个字符(str[i-j]~ str[i-1])与开头的j个(str[0]~str[j-1])相同
①如果str[j]==str[i]的话，说明尾部加入的字符使得上一轮最大公共子串向后延了一位，next[i]=j+1(此时j=next[i-1])

②若str[j]!=str[i]，说明加入的字符不能接在上一轮最大公共子串后面，尝试缩小公共子串，所以不断获取最大公共子串的最大公共子串，直至最大公共子串前缀串后面的字符与str[i]匹配上或j==0（str[i]这一段没有最大公共子串），那么就退出循环

注意：不能使用j - -

while(B[j]!=B[i]&&j>0)
	j=nex[j-1];//不能换成j--

KMP算法最浅显理解——一看就明白
这篇博客里提到了，但并没有说为什么。
因为使用j - -求出的不保证是str[0]到str[i-1]这一段字符串的公共子串，而是str[0]到str[i-1]这一段字符串的前缀后缀最大公共部分的前XX个字符，新加入的str[i]字符不可以接在这一段后面。

其他疑问

KMP的原理正确性？

如何更好的理解和掌握 KMP 算法? - 咸鱼白的回答 - 知乎

这篇回答为什么要求new数组？

KMP的其他优化形式