数据结构串的KMP模式匹配（C语言代码）

void get_next(char* pattern, int leng, int* next)
{
	int i = 0, j = -1;
	next[0] = -1;
	while (i < leng -1)
	{
		if (j == -1 || pattern[i] == pattern[j])
		{
			i++;
			j++;
			next[i] = j;
		}
		else
		{
			j = next[j];
		}
	}
}
void KMP_Match(const char* test, const char* pattern)
{
	int testlength = strlen(test);
	int patternlenth = strlen(pattern);
	int* next = (int*)malloc(sizeof(int) * patternlenth);
	if (next == NULL)
	{
		perror("error");
		exit(1);
	}
	get_next(pattern, patternlenth, next);
	int i = 0, j = 0;
	while (i<testlength)
	{
		if (j == -1 || test[i] == pattern[j])
		{
			i++;
			j++;
			if (j == patternlenth)
			{
				printf("第%d位为子串\n", i - j);
			}
		}
		else
		{
			j = next[j];
		}
	}
}
int main()
{
	char test[] = "ABABDABACDABABCABAB";
	char pattern[] = "ABABCABAB";
	KMP_Match(test, pattern);
	return 0;
}

 //nextval代码如下

void get_nextval(char* pattern, int leng, int* nextval)
{
	int j = 0, k = -1;
	nextval[0] = -1;
	while (j<leng-1)
	{
		if (k == -1 || pattern[j] == pattern[k])
		{
			j++;
			k++;
			if (pattern[j] != pattern[k])
			{
				nextval[j] = k;
			}
			else {
				nextval[j] = nextval[k];
			}
		}
		else
		{
			k = nextval[k];
		}
	}
}