#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;  //重新初始化，寻找下一个
			//i = i - plen + 1;  //i定位到该位置，外层for循环i++可以继续找下一个（这里默认存在两个匹配字符串可以部分重叠)。

			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 而退出循环， 要么因为字符相同而退出循环
			k = next[k];	//k回溯，后缀的最后一个字符不符合，直接调回前缀的长度处继续比较

		if (ptr[k + 1] == ptr[i]) //如果是因为字符相同（即：ptr[k + 1] == ptr[i]），则 k = k + 1,说明 k + 1 时符合
			k = k + 1;

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