kmp算法实现，next数组的一些理解

理解next数组要先理解两个字符串匹配的kmp算法实现

kmp算法中 一个串为匹配串，一个串为模式串，

next数组同样是利用了kmp算法的实现，只不过他是自己匹配自己然后，自己的后缀为匹配串，前缀为模式串，

这个过程就可以理解为一个递归的过程

当两个字符串不适配的时候，回溯回退的位置始终是模式串的不适配字符的上一位字符前后缀相同的位置，求next数组，前缀与后缀不适配时，同样是移动模式串，只不过这个模式串是自身的前缀部分.而视频中的len恰好指向了前缀部分，但是要找自身的前一位 所以prefix【len-1】

 

kmp代码模板：

#include<bits/stdc++.h>
using namespace std;
//此前缀后缀表第一位下标为0 没有用-1代替第一位，前缀后缀表也没有移位置 
void prefix_table(char pattern[],int prefix[],int n){//prefix就是前后缀匹配表 
	prefix[0]=0;
	int len=0;
	int i=1;
	while(i<n){
		if(pattern[i]==pattern[len]){//此时是前缀和后缀相等的时候 
			len++;
			prefix[i]=len;
			i++;
		}
		else{//不相等时
			if(len>0){
				len=prefix[len-1]; //此时找到前缀部分的上一个位置、 递归（始终是用模式串去回溯 next数组就和kmp数组一样 都是用模式串去回溯） 
								   //只不过next数组模式串为自身的前缀部分，所以我只用回溯next数组的前缀部分			
			} //len还有为0的情况如果不单独作界限判定会导致越界
			else{
				prefix[i]=len;                     
				i++;
			} 
			
		}
		
	}
}
//next数组改进就不用找前缀部分的上一个位置 直接第一个位置为-1然后集体右移动
void move_prefix_table(int prefix[],int n){
	int i;
	for(int i=n-1;i>0;i--){
		prefix[i]=prefix[i-1];
	}
	prefix[0]=-1;
} 

void kmp_search(char text[],char pattern[]){
	int n=strlen(pattern);
	int *prefix=(int *)malloc(sizeof(int)*n);//分配prefix长度 
	prefix_table(pattern,prefix,n);
	move_prefix_table(prefix,n);
	int j=0; //指向模式串 
	int i=1;//指向匹配串 
	int m=strlen(text);
	while(i<m){
		if(j==n-1&&text[i]==pattern[j]){//当匹配的模式串的最后一个字符相等时 
			printf("found pattern at %d\n",i-j);//找到了匹配串匹配到的模式串开始的下标 
			j=prefix[j];
		}
		if(text[i]==pattern[j]){
			i++;j++;
		}else{
			j=prefix[j];
			if(j==-1){
				i++;j++;
			}
		}
	}
}
int main(){
	char pattern[]="ABABCABAA";
	char text[]="ABABABCABAABABABAB";
//	int prefix[9];
//	int n=9;
//	prefix_table(pattern,prefix,n);
//	move_prefix_table(prefix,n);
//	for(int i=0;i<n;i++)
//		cout<<prefix[i]<<endl;
	kmp_search(text,pattern);
	return 0;
	
}