kmp.cpp

这是计算机专业硕士生课程《算法设计与实现》中讲到的模式匹配算法的实现

#include<iostream.h>
#include<string.h>
#include"interface.h"

void fail(char *pattern, int len_pat,int f[])
{
	f[0] = -1;
	for(int j=1;j<len_pat;j++)
	{
		int i=f[j-1];
		while(*(pattern+j) != *(pattern+i+1) && i >= 0)
			i=f[i];
		if(*(pattern+j) == *(pattern+i+1))
			f[j] = i+1;
		else f[j] = -1;
	}
}

int KMP(char *target,int len_targ,char *pattern,int len_pat,int *f)
{
	int posP = 0,posT = 0;
	
	fail(pattern,len_pat,f);
	while(posP < len_pat && posT < len_targ)
		if(pattern[posP] == target[posT])
		{
			posP++;
			posT++;
		}
		else if(posP == 0)
			posT++;
		else
			posP = f[posP-1]+1;

		if(posP < len_pat)
			return -1;
		else 
			return posT-len_pat;			
}

void testKMP(char *a,char* b)
{	
	int result;
	int *f;

	f = new int[strlen(b)];
	result = KMP(a,strlen(a),b,strlen(b),f);
//	cout<<"Pattern Matching:\n";
//	cout<<a<<endl<<b<<endl;

	if(result>-1)
	{
		cout<<"The KMP result is:"<<result<<endl;
		cout<<"After Matching:\n";
		cout<<a<<endl;
		for(int i=0;i<result;i++)
			cout<<" ";
		cout<<b<<endl;
	}	
	delete f;
}