数据结构串之——KMP算法

本文主要是介绍数据结构串之——KMP算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一：串的模式匹配

	即给定两个字符串S和T，一个设定为主串，一个设定为副串，我们要做的是在这
个主串S中找到子串T的位置。

二：朴素的模式匹配算法

	这是最简单的，也是我们最容易想到的，即遍历主串的每一个字符，在哪个字符
就在哪个字符停下来，从主串这个位置开始向后的字符串与副串相对比，如果途中遇
到了一个不同的字符，则将主串的字符向后遍历一位并继续进行对比操作，如果主串
中的某一段字符与副串的字符全依次相等，则子串在主串中的位置即为当前在主串中
遍历到的那个字符的位置。
	
下图：S串：abcababca...      T串：abcabx		

1：上图中第一步操作：前 5 个字符完全相等，第 6 个字符不等，但是我们可以看
到：T串的第 1 个字符和T串的第 2 和 3 个字符不相同，且在第一步操作中两串的
第 2 和 3 个字符是相同的，因此步骤 2 和 3 的比较是多余的。

2：T串中，第 1 个字符与第 4 个字符相等，为 ‘a’ ，第 2 位字符与第 5 位字符
相等，为 'b' , 且在步骤一中，T串中的第 4 和 5 个字符与S 串是对应相等的，
所以步骤 4 和 5也是多余的。

3：对比一下步骤 1 和步骤 6 ，我们发现，主串当前位置的下标均为 6，即i值为6，
同理在步骤 2，3，4，5中，i值为： 2，3，4，5。所以我们可以知道：在朴素算法
中，主串的 i 值是不断地回溯来完成的，但是我们上面说了，步骤 2，3，4，5均可
以省略，并且我们后面说道的KMP算法就是为了让这没必要的回溯不发生.

在kmp算法中，既然 i 值不回溯，即不会变小，所以我们要考虑的单只有 j 值了，并且我们在上面说了很多 T 串的首字符与自身后面字符的比较，如果发现有想等的字符，j 值的变化就会不同，所以这个 j 值的变化就不会不同。所以，这个 j 值的变化其实和主串没有啥关系.

三：KMP 模式匹配算法

:1：预说明

	一些教材里的讲解的前提是：副串的第一个位置存储的是副串的长度，在这里我
说的是：第一个位置不储存副串的长度。其实两种方式的原理都是相同的，两者的差
别只是相差了一个字符的位置。

2：next数组值的计算公式：
但是在这里我不会讲解这个公式。

3：最长前后缀

问：abcabfabcab中最长相等前后缀是什么呢？
答：abcab

	这个我也不太会描述，大家看上面的例子应该也能看懂，最长最前后缀在KMP算
法中非常重要.

4：图解KMP算法

下面设：
主串S为：abcabfabcab
副串T为：abcabexy

绿色背景：代表两者相匹配的字符。
黄色背景：代表两者不匹配的字符。
灰色背景：因为前面的不匹配这个区域停止与主串对比。

然后我们需要进行移动副串来继续进行比较操作，但是我们这里是像朴素匹配算法那样逐个移动吗？不是，在上面的朴素匹配算法中我们讲过了会有很多多余的操作。

事实上，每一个字符前的字符串都有最长相等前后缀，而且最长相等前后缀的长度是我们移位的关键，所以我们单独用一个next数组存储子串的最长相等前后缀的长度，并且next数组的数值只与子串本身有关。

是否还记得上面的 ‘最长公共前后缀’ 这个概念，在这里，在绿色区域寻找其最长的相等前后缀，很简单，这里为：‘ab’。并且结合上述：副串的第1个字符和第2、3字符均不同，所以结合了我们上面说的多余操作情况，我们下一步移动之后的比较情况应该为：

也就是让S[5]与S[5]前面字符串的最长相等前缀后一个字符再比较，而该字符的位置就是t[？],很明显这里的？是2，就是不匹配的字符前的字符串最长相等前后缀的长度。
所以，不匹配的字符处的next数组next【5】中存放的是子串回溯后应该对应的字符下标。

	next数组有以下两个作用：
	
1：存放该字符前的字符串的最长相等前后缀的长度。
2：表示该字符不匹配时应该回溯该字符的哪个下标位置的字符。

5：KMP算法的时间复杂度

设主串的长度为a，副串的长度为b。
时间来源有两部分：求next数组的时间 + 与主串比较的时间。
1：求next数组的时间复杂度 O(b)
2：与主串相较的时间复杂度为 O(a)
所以最终的时间复杂度为：O(a+b)

6：求next数组代码

	特殊情况：T[0]字符前没有其它字符，其next[0] = -1.

void GetNext(char string[], int *next) {
	//string接收的副串
	int i = 0;		//i代表是在
	int j = -1;
	next[0] = -1;	//string[0]为第一个字符，第一个字符为特殊情况
	while(i < string.length){
		if(j == -1 || string[i] == string[j]) {
			/*j = -1,说明和string[1]这个字符的情况相同，string[1]为第二个
			字符，其前面只有一个字符，根本不存在前后缀字符*/
			//string[i] == string[j]即为有相等前后缀字符
			i++;
			j++;
			//i,j均加1，代表两指针均向后移动一位
			next[i] = j;
		}
		else {
			//这是出现了字符不等的情况
			j = next[j]
			/*上面我们已经说过了，如果该字符不匹配时应该回溯该字符的哪个下标
			位置的字符。*/
		}
	}
}

j = next[j] 解析：

四：KMP算法的改进

1：为什么已经如此强大的KMP算法还需要改进呢？，请看下面的解释

		如果我们的主串 S='aaaabcde'，子串 T = 'aaaaax'，则在进行第一次
	比较操作时，两者的第5位字符不相等。

虽然可以很快的求出next数组的数值，但是其实我们会发现，第2,3,4,5这四个步骤其实是多余的，因为T串的第二、三、四、五位置的字符都与首字符 ‘a’ 相等，因此我们可以用首位字符的next数值去取代与它相等的字符后续的next[j]，所以我们对next数组进行改良操作，假设取代的数组为nextval数组。

KMP算法的改进算法的解析：如果某位字符a同该位字符的next数值指向的那位字符b相等，则nextval[a] = nextval[b]，如果不相等的话，nextval[a] = next[a]

2：代码部分

void get_nextval(char string[], int *next) {
	int i = 0;
	int j = -1;
	nextval[0] = -1;	 
	while(i < string.length) {
		if(j == -1 || string[i] == string[j]) {
				i++;
				j++;
				if(string[i] != string[j]) {
//这里的string[j]是string[i]处字符不匹配而会回溯到的字符
//为什么？因为没有这处if判断的话，此处代码是next[i]=j;
//next[i]就是string[i]不匹配时应该回溯到的字符位置
					nextval[i] = j;
				}
				else {
					nextval[i] = nextval[j]
				}
/*若不匹配的话，此时nextval[i]的值就是不匹配时回溯到的那个字
符的nextval值，因此如果不同的话，这里回溯了两次*/			
		}
		else {
			j = nextval[j];
		}
	}
}

这篇关于数据结构串之——KMP算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！