KMP算法C语言实现

#include
#include

#define maxsize 100

typedef struct
{
	char data[maxsize];
	int length;
}sqString;

void get_next(sqString t, int next[])
{
	int i = 0;
	int j = -1;
	t.length = strlen(t.data);
	next[0] = -1;
	while (i < t.length - 1)
	{
		if (j == -1 || t.data[i] == t.data[j])
		{
			i++;
			j++;
			next[i] = j;
		}
		else
		{
			j = next[j];
		}
	}
}

int KMP(sqString t1,sqString t2,int next[])
{
	int i=0, j=0;
	int len1 = strlen(t1.data);
	int len2 = strlen(t2.data);
	while (i < len1 && j < len2)
	{
		if (j == -1 || t1.data[i] == t2.data[j])
		{
			i++;
			j++;
		}
		else
		{
			j = next[j];
		}
	}
	if (j >= len2)
		return i - len2 + 1;
	else
		return -1;
}
int main()
{
	int i = 0;
	int next[100];
	sqString t1, t2;
	printf("请输入主串:");
	scanf("%s",t1.data);
	printf("请输入副串:");
	scanf("%s", t2.data);
	
	get_next(t2, next);

	i = KMP(t1, t2, next);
	printf("%dn", i);
	return 0;
}