/********************************************************************
	created:	2006/07/02
	filename: 	KMP.cpp
	author:		李創
                http://www.cppblog.com/converse/
				
				參考資料: 嚴蔚敏<<數據結構>>

	purpose:	KMP字符串匹配算法的演示
*********************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>

#define MAX_LEN_OF_STR	30			// 字符串的最大長度

typedef struct String				// 這里需要的字符串數組,存放字符串及其長度
{
	char	str[MAX_LEN_OF_STR];	// 字符數組
	int		length;					// 字符串的實際長度
}String, *PString;

// 得到字符串的next數組
void GetNextArray(PString pstr, int next[])
{
	assert(NULL != pstr); 
	assert(NULL != next);
	assert(pstr->length > 0);

	// 第一個字符的next值是-1,因為C中的數組是從0開始的
	next[0] = -1;
	for (int i = 0, j = -1; i < pstr->length - 1; )
	{
		// i是主串的游標,j是模式串的游標
		// 這里的主串和模式串都是同一個字符串
		if (-1 == j ||						// 如果模式串游標已經回退到第一個字符
			pstr->str[i] == pstr->str[j])	// 如果匹配成功
		{
			// 兩個游標都向前走一步
			++i;
			++j;
			// 存放當前的next值為此時模式串的游標值
			next[i] = j;
		}
		else								// 匹配不成功j就回退到上一個next值
		{
			j = next[j];
		}
	}
}

// KMP字符串模式匹配算法
// 輸入: S是主串,T是模式串,pos是S中的起始位置
// 輸出: 如果匹配成功返回起始位置,否則返回-1
int KMP(PString S, PString T, int pos)
{
	assert(NULL != S);
	assert(NULL != T);
	assert(pos >= 0);
	assert(pos < S->length);
	
	if (S->length < T->length)
		return -1;

	printf("主串\t = %s\n", S->str);
	printf("模式串\t = %s\n", T->str);

	int *next = (int *)malloc(T->length * sizeof(int));
	// 得到模式串的next數組
	GetNextArray(T, next);

	int i, j;
	for (i = pos, j = 0; i < S->length && j < T->length; )
	{
		// i是主串游標,j是模式串游標
		if (-1 == j ||				// 模式串游標已經回退到第一個位置
			S->str[i] == T->str[j]) // 當前字符匹配成功
		{
			// 滿足以上兩種情況時兩個游標都要向前進一步
			++i;
			++j;
		}
		else						//  匹配不成功,模式串游標回退到當前字符的next值
		{
			j = next[j];
		}
	}

	free(next);

	if (j >= T->length)
	{
		// 匹配成功
		return i - T->length;
	}
	else
	{
		// 匹配不成功
		return -1;
	}
}

int main(void)
{
	String S, T;

	strcpy(S.str, "acabaabaabcacaabc");
	S.length = strlen(S.str);

	strcpy(T.str, "abaabcac");
	T.length = strlen(T.str);

	int pos = KMP(&S, &T, 0);
	if (-1 == pos)
	{
		printf("無匹配!\n");
	}
	else
	{
		printf("pos = %d\n", pos);
	}
	
	system("pause");

	return 0;
}