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

int KMP(char *str, int len_s, char *ptr, int len_p);
int Cal_Next(char *ptr, int len, int *next);

int main()
{	
	char *str = "bacbababadababacambabacaddababacasdsd";
    char *ptr = "ababaca";
    int a = KMP(str, 36, ptr, 7);
	printf("a = %d\n",a);
	return 0;
}

int KMP(char *str, int len_s, char *ptr, int len_p)
{
	int i, k = -1;
	int *next = (int*)malloc(len_p * sizeof(int));

	Cal_Next(ptr, len_p, next);  //調(diào)用函數(shù)，計算next數(shù)組

	for (i = 0; i < len_s; i++)
	{
		while (k > -1 && ptr[k + 1] != str[i]) //str 與 ptr 不匹配，且 k != -1 
			k = next[k]; //回溯 k 

		if (ptr[k + 1] == str[i]) //因當前項匹配而退出循環(huán)， 即 ptr[k + 1] == str[i]
			k = k + 1;	// k 值加一

		if (k == len_p - 1) // 遍歷完全部的 ptr 數(shù)組，都匹配
		{
			//printf("在位置 %d\n",i-plen+1);
			//k = -1;  //重新初始化，尋找下一個
			//i = i - plen + 1;  //i定位到該位置，外層for循環(huán)i++可以繼續(xù)找下一個（這里默認存在兩個匹配字符串可以部分重疊)。

			return (i - len_p + 1);  //返回 ptr 在 str 中的位置
		}
	}
	return -1;  // 未有匹配項， 返回 -1
}

int Cal_Next(char *ptr, int len, int *next)
{
	int k = -1, i;
	next[0] = -1;
	for (i = 1; i < len; i++) //從第二個開始，因為第一個只有一個字符，必定無相同的最大前綴和最大后綴，初始化為-1
	{
		while (k > -1 && ptr[k + 1] != ptr[i]) //要么因為 k = -1 而退出循環(huán)， 要么因為字符相同而退出循環(huán)
			k = next[k];	//k回溯，后綴的最后一個字符不符合，直接調(diào)回前綴的長度處繼續(xù)比較

		if (ptr[k + 1] == ptr[i]) //如果是因為字符相同（即：ptr[k + 1] == ptr[i]），則 k = k + 1,說明 k + 1 時符合
			k = k + 1;

		next[i] = k; //將新的 k 值賦值
	}
}