KMP算法中的几个疑问

KMP算法next数组求解实现

首先我们通过应用场景将KMP算法中用到的名词做一个说明：

在一个字符串(string1)中查询是否存在另一个字符串(string2)。

在字符串匹配算法中，我们通常将字符串string1成为主串；字符串string2成为子串。

下面我们将分别说明朴素模式匹配算法和KMP算法，并重点说明KMP中next的求解方式。

1. 朴素模式匹配算法

朴素模式匹配算法步骤：

• 从主串第一个元素和子串第一个元素开始匹配，
• 如果相等，同时后移匹配后续字符；
• 如果不相等，主串指针和子串指针同时回溯(子串回溯到第一个元素，主串回溯到开始匹配元素的下一个元素)，之后重复这三个步骤。

效果图：




朴素匹配算法的C代码实现如下：

int findMatch(char *Str, char *match)
{
	int i=0, j=0;
	/*注意：这里下标从0开始计算*/
	while(i < strlen(Str) && j < strlen(match)){
		if(Str[i] == match[j]){
			i++;
			j++;
		}else{
			i = i - j + 1;
			j = 0;
		}
	}
	if( j == strlen(match)){
		return i - j;/*指出匹配成功的主串上的位置*/
	}else{
		return -1;/*匹配失败*/
	}
}

2. KMP算法

计算机界的先人们认为上述的匹配算法由于主串和子串指针在元素不相等时需要同时回溯，导致匹配效率低下。经过他们的一系列研究，提出了KMP匹配算法。该算法在匹配时无需主串指针进行回溯，执行回溯子串指针即可。

KMP是通过提前求取子串的特征来优化匹配流程的，该特征我们称之为next数组。它的作用是：当某一位置元素不匹配时，通过next数组来确定子串指针回溯的位置，从而避免每次都从子串的第一个元素开始。

KMP算法步骤：

• 获取子串的next数字信息
• 字符串匹配
  • 如果两个元素相等，同时向后移动指针，匹配后续字符
  • （如果主串元素与子串第一个元素都不等，则向后移动主串指针）
  • 如果两个元素不相等，则回溯子串指针，回溯到的位置为next中当前位置对应的值
  • 重复上述三个步骤

同样以上述例子为例进行说明：

KMP算法C代码实现如下：(代码实现上从0开始)

int getNext(char *str, int next[])
{
	int i = 0;
	int j = -1;

	if(!str || !next){
		printf("Parameters can't be NULL or can't be zero\n");
		return -1;
	}
	/*  下标从1开始
	**  index : 1 2 3 4 5 6 7 8 9  --i
	**	value : a b a b a a a b a
	**	next  : 0 1 1 2 3 4 2 2 3  --j
	**/
	/*  下标从0开始
	**  index : 0 1 2 3 4 5 6 7 8  --i
	**	value : a b a b a a a b a
	**	next  :-1 0 0 1 2 3 1 1 2  --j
	**/
	/*  next回溯
	**  index : 0 1 2 3 4 5 6 7 8
	**	value : a b a b a a a b a
	**				a b a b a a a b a
	**/
	next[0] = -1;
	printf("%2.2d  ", next[0]);
	while(i < strlen(str)-1){
		if(j == -1 || str[i] == str[j]){
			i++;
			j++;
			next[i]=j;
			printf("%2.2d  ", next[i]);
		}else{
			j = next[j];
		}
	}
	printf("\n");
	return 0;
}
//	char *str="ababaaaaba";
//	char *match="aaa";
int kmp(char *Str, char *match)
{
	int i=0,j=0;

	int next[100] = {0};

	int ret =getNext(match, next);
	if(ret != 0){
		printf("Get next error\n");
		return -1;
	}
	while(i<(int)strlen(Str) && j<(int)strlen(match)){
			if(j == -1 || Str[i] == match[j]){
				i++;
				j++;
			}else{
				j = next[j];
			}
	}
	if(j == strlen(match)){
		return i - j;
	}else{
		return -1;
	}
}

3. next数组的求解

很多书上在讲解KMP算法时，元素都是从1开始的，而实际使用过程中都是从0开始的。这个并不是什么问题，除此之外，对于代码的实现也遇到了疑问，下面我将个人在学习KMP的疑问记录下来：

• i,j下标的初值
• 从0开始与从1开始的区别
• next数组第一个元素的值设置依据
• 两个元素不等时，j为什么要如此回溯？

下面对这几个疑问进行说明：

int getNext(char *str, int next[])
{
	int i = 0;
	int j = -1;

	if(!str || !next){
		printf("Parameters can't be NULL or can't be zero\n");
		return -1;
	}
	next[0] = -1;
	while(i < strlen(str)-1){
		if(j == -1 || str[i] == str[j]){
			i++;
			j++;
			next[i]=j;
		}else{
			j = next[j];
		}
	}
	return 0;
}

3.1 j=next[j]的理解

next数组用来表示当前字符之前的串相似程度。那个如果对相似度进行量化呢？这里我们使用下标来量化相似度。例如：

下标	1	2	3	4	5	6	7	8	9
a	b	a	b	a	a	a	b	a
next数组	0	1	1	2	3	4	2	2	3

上表默认下标从1开始，这也是很多讲解KMP算法时的经常的方式。

什么叫使用下标来量化相似度呢？

比如第5个元素之前的字符串为"abab",它的前后相似的串为"ab", 因此当遇到以下情况时，

主串	a	b	a	b	c	d	e	f	g	i	j
子串	a	b	a	b	b
匹配情况	√	√	√	√	×
next	0	1	1	2	3

直接从子串的第三个元素开始比较即可(S[5] == T[3] ?)，而无需从第一个元素进行(前面元素通过next数组能保证一定相等)：

主串S	a	b	a	b	c	d	e	f	g	i	j
子串T			a	b	a	b	b
匹配情况					☆
			0	1	1	2	3

next的值代表如果主串和子串元素不等时，主串位置i无需回溯,只需要将子串位置回溯，回溯的位置下标就是对应next数据的值。也就是代码中的j=next[j]。

那么j=next[j]怎么理解呢？

这里有个默认前提：对子串递归使用KMP。这样就比较容易理解j=next[j]。

比如在求取第5个位置的next的值时：

已知第五个元素时，需要知道前四个元素的相似度，在第四个元素时我们已经知道T[1]=T[3], 现在只需要比较T[2] == T[4] ?即可，如果相等，那么next[5]=next[4]+1; 如果不相等，比如"ab"!=“ac”,那么就应该回溯到第一个位置的值，即j=next[j]

下标	1	2	3	4	5	6	7	8	9
子串T	a	b	a	c	c	a	a	b	a
子串T			a	b	a	b	c	a	a
next	0	1	1	2	?

3.2 next数组第一个位置的值

next的第一个值无法进行计算，因为它之前没有元素，就没有办法计算相似度。这里是设置默认值的。

那么默认值的要求是什么呢?

我们已经知道next的实际上就是下标，而next的第一个元素的值不得与现有的下标冲突：

• 如果下标从1开始，则next[1]可以是小于1的任意整数，因此默认使用0。此时ij的初始值分别为i=1;j=0;
• 如果下标从0开始，则next[0]可以是小于0的任意整数，因此默认使用-1。此时ij的初始值分别为i=0;j=-1;

4. 代码

下面列出完整的实现(包括KMP和朴素匹配算法，下标从0开始)

/*************************************************************************
             > File Name: kmp.c
             > Author: Toney Sun
             > Mail: [e-mail]
       > Created Time: 2020年06月27日 星期六 21时07分12秒
 ************************************************************************/

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int getNext(char *str, int next[])
{
	int i = 0;
	int j = -1;

	if(!str || !next){
		printf("Parameters can't be NULL or can't be zero\n");
		return -1;
	}
	/*
	**  index : 1 2 3 4 5 6 7 8 9  --i
	**	value : a b a b a a a b a
	**	next  : 0 1 1 2 3 4 2 2 3  --j
	**/
	/*
	**  index : 0 1 2 3 4 5 6 7 8 9  --i
	**	value : a b a b a a a b a
	**	next  :-1 0 0 1 2 3 1 1 2  --j
	**/
	/*
	**  index : 0 1 2 3 4 5 6 7 8
	**	value : a b a b a a a b a
	**				a b a b a a a b a
	**/
	next[0] = -1;
	printf("%2.2d  ", next[0]);
	while(i < strlen(str)-1){
		if(j == -1 || str[i] == str[j]){
			i++;
			j++;
			next[i]=j;
			printf("%2.2d  ", next[i]);
		}else{
			j = next[j];
		}
	}
	printf("\n");
	return 0;
}
//	char *str="ababaaaaba";
//	char *match="aaa";
int kmp(char *Str, char *match)
{
	int i=0,j=0;

	int next[100] = {0};

	int ret =getNext(match, next);
	if(ret != 0){
		printf("Get next error\n");
		return -1;
	}
	while(i<(int)strlen(Str) && j<(int)strlen(match)){
			if(j == -1 || Str[i] == match[j]){
				i++;
				j++;
			}else{
				j = next[j];
			}
	}
	if(j == strlen(match)){
		return i - j;
	}else{
		return -1;
	}
}

int findMatch(char *Str, char *match)
{
	int i=0, j=0;

	while(i < strlen(Str) && j < strlen(match)){
		if(Str[i] == match[j]){
			i++;
			j++;
		}else{
			i = i - j + 1;
			j = 0;
		}
	}
	if( j == strlen(match)){
		return i - j;
	}else{
		return -1;
	}
}

void main(int argc, char *argv[])
{
	char *str="ababaaaaba";
	char *match="c";

	int index = kmp(str, match);
	printf("-------index=%d------\n",index);

	index = findMatch(str, match);
	printf("-------index=%d------\n",index);	

}