KMP algorithm

LeetCode: KMP algorithm
	#include
	#include
	#include
	int *compute_prefix_function(char *pattern, int psize)
	{
	int k = -1;
	int i = 1;
	int *pi = malloc(sizeof(int)*psize);
	if (!pi)
	return NULL;
	pi[0] = k;
	for (i = 1; i < psize; i++) {
	while (k > -1 && pattern[k+1] != pattern[i])
	k = pi[k];
	if (pattern[i] == pattern[k+1])
	k++;
	pi[i] = k;
	}
	return pi;
	}
	int kmp(char *target, int tsize, char *pattern, int psize)
	{
	int i;
	int *pi = compute_prefix_function(pattern, psize);
	int k = -1;
	if (!pi)
	return -1;
	for (i = 0; i < tsize; i++) {
	while (k > -1 && pattern[k+1] != target[i])
	k = pi[k];
	if (target[i] == pattern[k+1])
	k++;
	if (k == psize - 1) {
	free(pi);
	return i-k;
	}
	}
	free(pi);
	return -1;
	}
	int main(int argc, const char *argv[])
	{
	char target[] = "ABC ABCDAB ABCDABCDABDE";
	char *ch = target;
	char pattern[] = "ABCDABD";
	int i;
	i = kmp(target, strlen(target), pattern, strlen(pattern));
	if (i >= 0)
	printf("matched @: %s\n", ch + i);
	return 0;
	}

Jump to Line