#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);  //調用函數，計算next數組

	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]) //因當前項匹配而退出循環， 即 ptr[k + 1] == str[i]
			k = k + 1;	// k 值加一

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

			return (i - len_p + 1);  //返回 ptr 在 str 中(zhōng)的位置
		}
	}
	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++) //從第二個(gè)開始，因為第一個(gè)隻有一個(gè)字符，必定無相同的最大前綴和(hé)最大後綴，初始化為-1
	{
		while (k > -1 && ptr[k + 1] != ptr[i]) //要麼因為 k = -1 而退出循環， 要麼因為字符相同而退出循環
			k = next[k];	//k回溯，後綴的最後一個(gè)字符不符合，直接調回前綴的長度處繼續比較

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

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