KMP算法的理解+板子

对kmp算法的理解中，很重要的一点就是next数组。

很多人不理解next数组的含义，是因为它同时具有两个意思，而且这两个意思在不同的环境下不同。

现在给你两个字符串：

一个是文本串 text

一个是模板串 pattern

然后定义两个指针，指针i 指向文本串。指针 j 指向模板串。

现在我们要找模板串在文本串中第一次出现的位置。

那么直接从文本串的第一个字符和模板串的第一个字符开始匹配。（i=text[0] , j=pattern[0])

如果i，j匹配成功（即 text[i] == pattern[j] )?

那么i，j都往右移动。

如果i , j 匹配不成功，那么我们希望 j能重新跳到模板串的某一个位置，重新开始匹配。

（这里不能让i跳，因为 i的变化必须保持是线性的）

如果我们能让 j 具备这样的功能的话，那么匹配字符串将是线性复杂度。

那么我们就提出了一个next数组，希望它能做到这件事。

不过要理解kmp

我们要搞清楚，next数组有什么含义？

• 如果i指针指向的字符 和 j指针指向的字符匹配失败，j指针应该去的位置（这里指的是j指针应该回到模板串的哪个下标）
• next[k] 表示在模板串中从0开始到下标为k，也就是[0,k]的字符串中，最长相等前后缀的长度。

为什么这样说？

其实，我们一开始定义next数组的时候，单纯的希望它有一个功能，就是如果文本串和模板串发生不匹配，那么指针j 去往的地方是 next[j-1] 。

(因为我们现在正在匹配 j ，说明j-1 是已经匹配成功了的，所，

然后我们在求解 next数组的时候发现：

next[k] 的值和? “在模板串中从0开始到下标为k的字符串中，最长相等前后缀“ 的长度相等。

说明我们就可以通过这个特点来求解next数组。

什么意思呢？ 假设我们现在已经求好了next数组的值，那么我们是不是可以根据next数组的含义（如果i指针指向的字符 和 j指针指向的字符匹配失败，j指针应该去的位置）

来写出kmp主函数？

int kmp(string text, string pattern) {//文本串，模板串

	//分别表示文本串和模板串的长度
	int tlen = text.size();
	int plen = pattern.size(); 


	vector<int > next=get_next(pattern);//next数组

	//假设我们已经得到了next数组，由于next数组的一个含义是，当匹配失败，模板串指针前往的位置
	//所以我们可以写出

	int  j = 0;
	for (int i = 0; i < tlen; i++) { //遍历一遍文本串，以线性的时间复杂度求出匹配位置
		if (pattern[j] == text[i]) {//如果匹配了，那么j，i都往右边移动
			j++;
			if (j == plen) { //如果模板串全部都匹配上了
				return i - j;//直接返回第一次匹配成功的下标
			}
		}
		else {//如果没匹配上
			if (j > 0) { //如果j大于0
				j = next[j - 1]; //j前往应该去的地方
			}
//否则，如果j等于0，那么它无处可以去。
		
		}
	}

	return -1; //如果扫完了一遍文本串还没匹配，直接返回-1
}

很好，根据next的数组的第一个含义我们能求出kmp函数。

但是我们怎么求next数组？ 只需要将next数组的性质结合起来即可。

在求next的数组中需要转变两种观点：

当不匹配的时候，把pattern[0,i]当作文本串、把patter[0,j] 看作模板串，就按照上面kmp的步骤来即可。当不匹配，直接让j=next[j-1]；

当i，j匹配， 那么说明 [0,j-1]肯定是已经匹配上了的（前提是j>0)，又[0,j-1]的长度是 j

现在j也匹配上了，那么最长相等前后缀长度不就 j+1 吗。

(也可以理解成如果 i，j 匹配上了，那么next[i]=next[i-1]+1、 因为匹配成功了一个新字符，那么最长公共前后缀长度+1）

所以啊，如果我们这样想的话，那么next数组也求完了。

vector<int > get_next(string pattern) { //求next数组，并返回next数组

	int plen = pattern.size();
	vector<int> next(plen);
	int i = 1, j = 0; //此时我们将[0,i]当作文本串，将[0,j]的串当作模板串
	

	for (int i = 1; i < plen; i++) {
		while (j > 0 and pattern[i] != pattern[j]) { //如果不匹配，那么j就退到应该去的，直到退到0，或者退到二者匹配
			j = next[j];
		}
		

		if (pattern[i] == pattern[j]) { //这里的话，next就代表[0,i]区间的最长公共前后缀
			next[i] = ++j;
		}
	}
	return next;

}

?然后，把二者合起来就是完整的板子了。