KMP算法实现（参考Wiki上算法描述）

#include <iostream>
using namespace std;

/**
* paramter pat:待匹配的字符串
* T: 返回的table
*
**/
void kmp_table(const char * W, int T[])
{
	int pos = 2;  //当前查找的位置
	int cnd = 0; //当前查找的前缀字串的位置


	T[0] = -1;
	T[1] = 0;

	while(pos < strlen(W))
	{
		if( W[cnd] == W[pos-1] ) 
		{
			T[pos] = cnd + 1;
			pos++;
			cnd++;
		}
		else if( cnd > 0 )
			cnd = T[cnd]; //回退，有难度

		else 
		{
			T[pos] = 0;
			++pos;
		}
	}

}

int kmp_search(const char * S,const char * W)
{
	int m = 0 ; //开始匹配的位置
	int i = 0 ; //W中位置

	int * T = new int[strlen(W)];



	kmp_table(W,T);

	for(int j = 0; j < strlen(W); j++)
	{
		cout << T[j] <<" ";
	}
	cout<<endl;

	while( (m + i) < strlen(S))
	{
		if(S[m+i] == W[i])
		{
			++i;
			if(i == strlen(W))
				return m;
		}
		else 
		{
			m = m + i - T[i];
			if( i > 0)  i = T[i];
		}
	}
}

int main()
{
	char * S = "acabaabaabcacaabc";
	char * W = "abaabcac";

	int p = kmp_search(S,W);

	cout<<"p = "<< p <<endl;
}