模式匹配之KMP算法

#问题描述

模式匹配:字串的定位操作通常被称为串的模式匹配

最简单的模式匹配方式：从主串S的第pos个字符起和模式的第一个字符比较之，若相等，则继续逐个比较后续字符；否则从主串S的下一个字符起再重新和模式的字符比较之。依次类推，直至模式T中的每个字符依次和主串S中的一个连续的字符序列相等，则称匹配成功，函数值为和模式T中第一个字符相等的字符在主串中的序号，否则称匹配失败。

模式匹配的改进算法

D.E.Knuth 、V.R.Pratt 和 J.H.Morris同时发现，其算法的本质改变在于：每当一趟匹配过程中出现字符比较不等时，不需要回溯指针，而是利用已经得到的部分匹配结果将模式向右移动尽可能远的一段距离后，继续进行比较。

在此不对算法本身做太多阐述，网上有很多说明，仅仅是，完成我自己在理解此算法之后，写出相应的代码。

求next与nextval与匹配

#include<stdio.h>
#include<string.h>
#include<malloc.h>
#include<memory.h>
#include<time.h>


void Next1(char *pattern, int next[]){
	int length=strlen(pattern);
	*(next)=0;
	*(next+1)=1;
	for(int i=2;i<length;i++){
		int aim=i-1;
		while(pattern[i-1]!=pattern[next[aim]-1]){
			aim=next[aim]-1;
			if(aim==0)
				break;
		}
		next[i]=next[aim]+1;
		
	}
	for(int i=1;i<length;i++){
		if(pattern[i]==pattern[next[i]-1])
			next[i]=next[next[i]-1];
	}

}


void NextVal(char *pattern, int next[]){
	int length=strlen(pattern);
	*(next)=0;
	*(next+1)=1;
	for(int i=2;i<length;i++){
		int aim=i-1;
		while(pattern[i-1]!=pattern[next[aim]-1]){
			aim=next[aim]-1;
			if(aim==0)
				break;
		}
		next[i]=next[aim]+1;
		
	}
	for(int i=1;i<length;i++){
		if(pattern[i]==pattern[next[i]-1])
			next[i]=next[next[i]-1];
	}

}



int Index_KMP(char *S,char *T,int pos){
	//利用模式串T的next函数求在主串S中第pos个字符开始匹配到的位置
	//返回-1时代表没匹配到
	int i=pos,j=0; //i是指主串的，j是指模式串的
	int *next=(int *)malloc(sizeof(int)*strlen(T));
	NextVal(T,next);//这个过程是O(m)的
	while(i<strlen(S)&&j<strlen(T)){//这个过程O(m+n)
		if(j==0||S[i]==T[j]){
			++i;++j;
		}else{
			j=next[j]-1;
		}
	}
	if(j>=strlen(T))
		return i-strlen(T);
	else
		return -1;
}



int main()
{
	char *a="aaaab";
	char *b="aaaaab";
	printf("a&b KMP position: %d",Index_KMP(b,a,0));
	int n=strlen(a);
	int *nex1,*nex2;
	nex1=(int *)malloc(sizeof(int)*n);
	memset(nex1,0,sizeof(nex1));
	nex2=(int *)malloc(sizeof(int)*(1+n));
	memset(nex2,0,sizeof(nex2));
	for(int k=0;k<100000;k++)
		Next1(a,nex1);
	for(int i=0;i<n;i++)
		printf("%d ",nex1[i]);
	printf("\n");
	for(int k=0;k<100000;k++)
		NextVal(a,nex2);
	for(int i=0;i<n;i++)
		printf("%d ",nex2[i]);
	printf("\n");
	
	return 0;
}