kmp.cpp

KMP,数据结构中快速搜索KMP算法的C语言实现

#include <iostream>
#include <string.h>
#include <malloc.h>
using namespace std;

int*		BuildNextTable(char	*P)
{
	int*		N = (int*) malloc(strlen(P) * sizeof(int)); //Next[]表

	int		j = 0; //主串指针
	int		t = N[0] = -1; //模式串指针

	while (j <(int) strlen(P)-1)
	{
		if (0 > t || P[j] == P[t]) 
		{ //匹配
			j++;	t++;
			N[j] = (P[j] != P[t]) ? t : N[t]; 
		} else //失配
			t = N[t];
	} //while

	return(N);
}

/*
*	KMP算法
************************************************************************/
int		PatternMatch( char	*P, char	*T)
{
	int*		next = BuildNextTable(P); //构造Next[]表

	int		i = 0; //主串指针
	int		j = 0; //模式串指针

	while(i <(int) strlen(T))
	{                                //自左向右逐个比较字符
		if (0 > j ||T[i] == P[j]) {//若匹配，或P已移出最左侧
			i++;	j++; //则转到下一字符
		} else 
		{ //否则
			j = next[j]; //模式串右移
		}
		if(j >=(int) strlen(P)) j=0;
	} //while
	free(next); //释放Next[]表

	return(i-j);
}