KMP模板

kmp算法是字符匹配问题，简单来说就是给你两个字符串，看其中一个字符串在另外一个字符串出现的位置，让你求出出现的起始位置和重复的次数。
kmp最核心的就是求出next数组，next数组的含义就是一个固定字符串的最长前缀和最长后缀相同的长度。
比如：abcjkdabc，那么这个数组的最长前缀和最长后缀相同必然是abc。
cbcbc，最长前缀和最长后缀相同是cbc。
abcbc，最长前缀和最长后缀相同是不存在的。
注意最长前缀：是说以第一个字符开始，但是不包含最后一个字符。
比如aaaa相同的最长前缀和最长后缀是aaa。
对于目标字符串ptr，ababaca，长度是7，所以next[0]，next[1]，next[2]，next[3]，next[4]，next[5]，next[6]分别计算的是
a，ab，aba，abab，ababa，ababac，ababaca的相同的最长前缀和最长后缀的长度。由于a，ab，aba，abab，ababa，ababac，ababaca的相同的最长前缀和最长后缀是“”，“”，“a”，“ab”，“aba”，“”，“a”,所以next数组的值是[-1,-1,0,1,2,-1,0]，这里-1表示不存在，0表示存在长度为1，2表示存在长度为3。这是为了和代码相对应。
下图中的1，2，3，4是一样的。1-2之间的和3-4之间的也是一样的，我们发现A和B不一样；之前的算法是我把下面的字符串往前移动一个距离，重新从头开始比较，那必然存在很多重复的比较。现在的做法是，我把下面的字符串往前移动，使3和2对其，直接比较C和A是否一样。

求next数组的模板

void next(char *str, int *next, int len)
{
    next[0] = -1;//next[0]初始化为-1，-1表示不存在相同的最大前缀和最大后缀
    int k = -1;//k初始化为-1
    for (int q = 1; q <= len-1; q++)
    {
        while (k > -1 && str[k + 1] != str[q])//如果下一个不同，那么k就变成next[k]，注意next[k]是小于k的，无论k取任何值。
        {
            k = next[k];//往前回溯
        }
        if (str[k + 1] == str[q])//如果相同，k++
        {
            k = k + 1;
        }
        next[q] = k;//这个是把算的k的值（就是相同的最大前缀和最大后缀长）赋给next[q]
    }
}

kmp模板

void cal_next(){
	next[0]=-1;
	int k=-1;
	for(int q=1;q<len1;q++){
		while(k!=-1&&a[q]!=a[k+1])k=next[k];
		if(a[q]==a[k+1])k=k+1;
		next[q]=k;
	}
	return ;
}
void KMP(){
	sum=0;
	int k=-1;
	for(int i=0;i<len2;i++){
		while(k!=-1&&b[i]!=a[k+1]) k=next[k];
		if(b[i]==a[k+1]) k=k+1;
		if(k==len1-1){
			sum++;//出现的次数累加 
			k=next[k];
			 //cout << "在位置" << i-len2+1<< endl;
            //k = -1;//重新初始化，寻找下一个
            //i = i - len2 + 1;//i定位到该位置，外层for循环i++可以继续找下一个（这里默认存在两个匹配字符串可以部分重叠）
            //return i-len2+1;//返回相应的位置
		}
	}
	return ;
}