KMP算法

一、问题引入

BF算法的平均时间复杂度过高，提出了一种新的匹配算法 KMP算法。

主串S的位置i 一直往下移动，不再回溯。但字串T的位置j 需要根据算法确定下来。

二、解决过程

• 函数：get_next()

void get_next(const char *T, int **next)
{
	int i = 0, j = -1;
	int T_len = strlen(T);
	(*next) = (int *)malloc(T_len * sizeof(int));
	memset(*next, 0, T_len * sizeof(int));
	(*next)[0] = -1;
	while (i < T_len-1)
	{
		if (j == -1 || T[i] == T[j])
		{
			++i;
			++j;
			(*next)[i] = j;
		}
		else
			j = (*next)[j];
	}
    // test 
	for (int i = 0; i < T_len; i++)
		printf("%d\t", (*next)[i]);
	printf("\n");
}

• 函数：index_kmp()

int index_kmp(const char *S, const char *T, int pos)
{
	/* pos的有效范围：0<=pos<=S_len-1 */
	int i = pos, j = 0;
	int *next = NULL;
	int S_len = strlen(S);
	int T_len = strlen(T);
	/* 串S和串T不为空串 */
	if (S_len == 0 || T_len == 0)
		return -1;
	if (pos < 0 || pos > S_len)
		return -1;
	get_next(T, &next);
	while (i < S_len && j < T_len)
	{
        printf("第%d轮: i=%d\tj=%d\n", ++count, i, j);  // test
		if (j == -1 || S[i] == T[j])
		{
			++i;
			++j;
		}
		else
		{
			j = next[j];
		}
	}
	free(next);
	if (j >= T_len)
		return i - T_len;
	else
		return -1;
}

• 函数：main()

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

int main(void)
{
	char S[] = {"hello world"};
	char T[] = {"ello"};
	int index; // index从0开始
	printf("S_String：%s\n", S);
	printf("T_String：%s\n", T);
	if (-1 == ( index = index_kmp(S, T, 0)))
	{
		printf("Not found\n");
	}
	else
	{
		printf("Found, index is %d\n", index);
	}
	return 0;
}