设：m是模式串pattern的长度，n是主串长度

传统的字符串匹配(暴力法)的时间复杂度是O(n*m)。

而KMP串匹配算法可以将时间复杂度降为O(n+m)，这需要一个额外的预处理O(m)。

KMP优化的地方在于：当出现字符失配的情况时，无需回溯i指针，而是利用已经匹配的部分，将模式串尽可能向右滑动一部分。

实际上：KMP的预处理本身就是一个模式串pattern“自我匹配”的过程。因此，预处理和kmp算法主体非常神似。

预处理过程：

int get_next(char* p, int* next)
{
	int len = strlen(p);	
	int i = 0, k = -1;
	next[0] = -1;
	while(i<len)
	{
		if(k==-1 || p[i]==p[k])
		{
			i++;
			k++;
			next[i] = k;
		}else
		{
			k = next[k];
		}
	}
}

KMP匹配算法，这里我们和书上的做了一点改进，加入了一个start，即可以支持在主串中查找多次模式串。代码如下：

int kmp_index(char* s, char* p, int* next, int start)
{
	int i=start,j=0;
	int slen = strlen(s);
	int plen = strlen(p);
	while(i<slen && j<plen)
	{
		if(j==-1 || s[i]==p[j])
		{
			i++;
			j++;
		}else
		{
			j = next[j];
		}
	}
	if(j>=plen)
	{
		return i-plen;
	}else
	{
		return -1;
	}
}

测试驱动如下：

int main()
{
	char* str = "xxabaabcacxxabaabcacdabaabcac99";
	char* pattern = "abaabcac";
	int next[MAX];
	int plen = strlen(pattern);
	int i;
	// Get next value
	get_next(pattern, next);
	for(i=0;i<plen;i++)
	{
		printf("%d ", next[i]);
	}
	printf("\n");
	// KMP Index
	i=0;
	while(i!=-1)
	{
		i = kmp_index(str, pattern, next, i);
		if(i!=-1)
		{
			printf("'%s' @ %dth of '%s'\n", pattern, i, str);
			i++;
		}
	}
	return 0;
}