#define _CRT_SECURE_NO_WARNINGS 1

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

int KMP(char *str, char *sub,int pos)
{
	if (str == NULL || sub == NULL) return -1;
	int lenstr = strlen(str);
	int lensub = strlen(sub);
	if (lenstr == 0 || lensub == 0 || lensub > lenstr) return -1;
	if (pos < 0 || pos >= lenstr)return -1;

	int* next = (int*)malloc(sizeof(int) * lensub);
	next[0] = -1;
	next[1] = 0;
	int i = 0, j = 0;
	int k = 0;

	//求next数组
	for (i = 1; i < lensub - 1; )
	{
		if (k == -1 || sub[k] == sub[i])
		{
			next[i + 1] = k + 1;
			++i;
			++k;
		}
		else
		{
			k = next[k];
		}
	}

	//求nextval数组
	for (i = 1; i < lensub; ++i)
	{
		if (sub[i] == sub[next[i]])
			next[i] = next[next[i]];
	}
	//打印数组
	/*for (i = 0; i < lensub; ++i)
	{
		printf("%d, ", next[i]);
	}*/

	//查找是否有子串
	i = pos;
	j = 0;
	while (i < lenstr && j < lensub)
	{
		if (j == -1 || str[i] == sub[j])
		{
			++i;
			++j;
		}
		else
		{
			j = next[j]; 
		}
	}
	if (j < lensub )
		return -1;
	return i - j;
}


int BF(char* str, char* sub, int pos)
{
	if (str == NULL || sub == NULL) return -1;
	int lenstr = strlen(str);
	int lensub = strlen(sub);
	if (lenstr == 0 || lensub == 0 || lensub > lenstr) return -1;
	if (pos <0 || pos >=lenstr)return -1;

	int i = pos, j = 0;
	while (i + lensub - 1 <= lenstr)  
	{
		j = 0;
		while (i < lenstr && j < lensub)
		{
			if (str[i] != sub[j])
			{
				break;
			}
			i++;
			j++;
		}
		if (j == lensub)
			return i-j;
		i = i-j+1;
	}
	return -1;
}

int main()
{
	char* s1 = "adereegfbw11111";
	char* s2 = "aaaab";
	printf("%d", KMP(s1, s2, 0));
}