#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<assert.h>
#include<string.h>
#include<stdlib.h>
void GetNext(char* sub, int* next,int lenSub)
{
	next[0] = -1;
	next[1] = 0;
	int i = 2;//当前i下标
	int k = 0;//前一项的k
	while(i<lenSub)
	{
		if (k==-1 || sub[i - 1] == sub[k])
		{
			next[i] = k + 1;
			i++;
			k++;
		}
		else
		{
			k = next[k];
		}
	}
}

/*
str 代表主串
sub 代表子串
pos 代表从主串的pos位置开始找
*/
int KMP(char* str, char* sub, int pos)
{
	assert(str != NULL && sub != NULL);
	int lenStr = strlen(str);//求主串的长度
	int lenSub = strlen(sub);//求子串的长度
	if (lenStr == 0 || lenSub == 0)
	{
		return -1;
	}
	if (pos<0 || pos>lenStr)
	{
		return -1;
	}
	int* next = (int*)malloc(sizeof(int) * lenSub);
	assert(next != NULL);
	GetNext(sub, next,lenSub);
	int i = pos;//遍历主串
	int j = 0;//遍历子串
	while (i < lenStr && j < lenSub)
	{
		if (j==-1 || str[i] == sub[j])
		{
			i++;
			j++;
		}
		else
		{
			j = next[j];
		}
	}
	if (j >= lenSub)
	{
		return i - j;
	}
	return -1;
}
int main()
{
	printf("%d", KMP("ababcabcdabcde", "dabcde", 0));//5  从第五个位置开始匹配
	return 0;
}



//nextval
//1.回退到的位置和当前字符一样，就写回退那个位置的next值
//2.如果回退到的位置和当前字符不一样，就写当前字符原来的next值