串——KMP算法

KMP算法比起BF算法，解决了指针回拨导致的效率降低。

算法的实现如下：

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

#define MAXSIZE 260

typedef struct {
	char data[1000];
	int length;
}String;

void GetNext(String str, int next[])
{
	int j = 0, k = -1;
	next[0] = -1;
	while(j < str.length - 1)
	{
		if(k == -1 || str.data[j] == str.data[k])
		{
			++j, ++k;
			next[j] = k;
		}
		else
		{
			k = next[k]; 
		} 
	}
}

signed int KMP(String str, String childStr)
{
	int next[MAXSIZE], i = 0, j = 0;
	GetNext(str, next);
	
	while(i < str.length && j < childStr.length)
		if(j == -1 || str.data[i] == childStr.data[j])
			++i, ++j;
		else
			j = next[j];

	if(j >= childStr.length)
	    return (i - childStr.length);
	return -1;
}

int main()
{
	String str1, str2;
	strcpy(str1.data, "helloworld");
	str1.length = strlen(str1.data);
	strcpy(str2.data, "owo");
	str2.length = strlen(str2.data);
	printf("%d", KMP(str1, str2));
	return 0;
}