#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);
}