原创

KMP算法知识梳理


KMP算法个人理解

最大公共前后缀的理解

getNext方法的代码

void getNext(char str[],int next[],int n){
 int len=0;
 int i=1;
 next[0]=0;
 while(i<strlen(str))
 {
  	if(str[i]==str[len])
	{
   	len++;
   	next[i]=len;
   	i++;
 	}
  	else
	{
		if(len>0)
		{
			len=next[len-1];
		}
		else
		{
     		next[i]=len;
	 		i++;
		}
 	}
 }
 }

void prefix_change(int next[],int n)
{
	int i=n-1;
	while(i>0)
	{
	next[i]=next[i-1];
	}
	next[0]=-1;
}

KMP匹配算法:


int KMP(int next[],char str1[],char str2[])
{
	int m,n,i,j;
	m=strlen(str1);
	n=strlen(str2);
	i=0;
	j=0;
	while(i<m)
	{
		if(j==n-1 && str1[i]==str2[j])
		{
			return i-j;
		}
		if(str1[i]==str2[j])
		{
			i++;
			j++;
		}
		else
		{
			j=next[j];
			if(j==-1)
			{
				j++;
				i++;
			}
		}
	}
}

学习