第五届第三题 信号匹配 KMP算法

#include<stdio.h>
#include<stdlib.h>

int* make_next(int pa[],int pn)
{
	int* next=(int*)malloc(sizeof(int)*pn);
	next[0]=-1;
	int j=0;
	int k=-1;
	while(j<pn-1){
		if(k==-1||pa[j]==pa[k]){
			j++;
			k++;
			next[j]=k;
		}
		else
		k=next[k];
	}
	return next;
 } 
 
 int find(int da[],int an,int pa[],int pn)
 {
 	int rst=-1;
 	int* next=make_next(pa,pn);
 	int i=0;
 	int j=0;
 	int n=0;
 	while(j<an){
 		n++;
 		if(da[i]==pa[j]||j==-1){
 			i++;
 			j++;
 			
		 }
		 else
		 j=next[j];
		 if(j==pn)
		 {
		 	rst=i-pn;
		 	break;
		 }
	 }
	 free(next);
	 return rst;
 }
 
 int main()
 {
 	int da[]={1,2,1,2,1,1,2,1,2,1,1,2,1,1,2,1,1,2,1,2,1,1,2,1,1,2,1,1,1,2,1,2,3};
 	int pa[]={1,2,1,1,2,1,1,1,2};
 	
 	int n=find(da,sizeof(da)/sizeof(int),pa,sizeof(pa)/sizeof(int));
 	printf("%d\n",n);
 	
 	return 0;
 }
 

翻了大二学的数据结构的书，竟然是KMP的源代码，一点都没变。

串的KMP算法 效率O（n+m）

其中最关键的是创建next数组，find函数的原理就是一一对应则举手说成功了，不对应则跳到该字符相应的next值处继续比对。

next[j]=k

则next[j]表明当模式中第j个字符与主串字符“失配”时，在模式中需重新和主串中该字符进行比较的字符的位置。

书上的定义：

next[j]={① 0，当j=1时

            ②Max{k|1<k<j且"p1...p(k-1)=p(j-k+1)...p(j-1)"}//也就是next[j]由第j-1个元素决定的

            ③1 ，其他时候

个人理解比较容易写出next数组的方法：

比如

根据定义，则next[1]=0，

j=2时，a在其之前找不到对应的元素，故为1；

j=3时，b在其之前找不到对应的元素，故为1；

j=4时，a可以找到与其相同的j=1处的a,有p1=p3;

则有p1..p(k-1)=p(j-k+1)..p(j-1) 则此时k=2；

j=5时，同j=4，k=2；

j=6时，有p1p2=p4p5，则k=3；

j=7时，c在其之前找不到对应的元素，故为1。

该题中，将next[0]设为-1。串是从0开始，书上定义则是从1开始的，所以一模一样~！

其对应的next数组为 ： -1 ，0，0，1，1，2，0