KMP算法实现

#include "StdAfx.h"
#include "KMP.h"

KMP::KMP(void)
{
	str = "dasfqwerfadfaslkfjoijmqwemlkefadfaslk";
	substr = "fadfas";
	this->next = new int[strlen(this->substr)+1];
}

KMP::~KMP(void)
{
	delete this->next;
}

void KMP::run()
{
	cout << this->str << endl;
	cout << this->substr << endl;
	computePrefix();

	int k = 0,i=0;
	int tLen = strlen(this->str);
	int pLen = strlen(this->substr);

	for(;i<tLen;i++)
	{
		while(k > 0 && (this->substr[k] != this->str[i]))
			k = this->next[k];
		if(this->substr[k] == this->str[i])
			k++;
		if(k == pLen)
		{
			cout << "Pattern occurs with position : " << i - pLen + 1 << endl;
			k = this->next[pLen-1];
		}
	}
}

void KMP::computePrefix()
{
	int len = strlen(this->substr);

	int k = 0,i=1;

	this->next[0] = 0;

	for(;i < len;i++)
	{
		while( k > 0 && (substr[k] != substr[i]))
			k = this->next[k];
		if(substr[k] == substr[i])
			k++;

		this->next[i] = k;
		cout << k << " ";
	}

	cout << endl;
}