KMP算法

算法介绍

KMP 算法是 D.E.Knuth、J,H,Morris 和 V.R.Pratt 三位神人共同提出的，称之为 Knuth-Morria-Pratt 算法，简称 KMP 算法。该算法相对于 Brute-Force（暴力）算法有比较大的改进，主要是消除了主串指针的回溯，从而使算法效率有了某种程度的提高。

使用KMP算法能够快速的找到目标串中的模式串。

时间复杂度为$O(m+n)$。

算法思路

首先，想要找到目标串中的模式串，很显然是有一种暴力方法的，就是通过j指针和k指针的不断移动，来判断是否存在该子串，如果相同，则j++，k++，如果不同，则j回退，并且向前移动一位,再继续匹配。

显然，这种方法十分易懂，但是时间复杂度太高了，根本不适合用于比较长的字符串比较。

那么，就提出来了KMP算法。

显然，C与B是配对失败的，当电脑使用之前的暴力算法的时候，便会前移一位。

很明显，这个前移是毫无意义的，因为第一位便无法匹配。

而当我们人自己来匹配的时候，当C与B匹配失败之后，很明显是不会回退到B再重新去配对的，因为前面的A已经被使用完了，而电脑不会思考，我们就需要想办法让j指针不动，而k指针回退到适当的位置，来缩短回溯的时间。

这样，这个算法最重要、最核心、也最难懂的地方——next数组，便是用来实现这个功能的。

NEXT数组

next数组的定义就是，数组第i位之前的i-1位的前缀和后缀相等的最大长度。

例如，模式串为

特殊的，为了方便计算，我们将next[0] = -1，取一个特殊数字。

先上代码

int next[maxn];

void getnext(string t){
	int j = 0, k = -1;
	int n = t.length();
	while (j < n) {
		if (k == -1 || t[j] == t[k]) {
			j++, k++;
			next[j] = k;
		}
		else k = next[k];//这句是最重要也最难懂的地方
	}
}

代码十分简短，但是却并不好理解。

分为几种情况

当k等于-1时，代表的是第一位之前，需要j++，k++，然后之后进行第一位的匹配。

当t[j]与t[k]相同的时候，j和k同时后移，记录最长的长度。

如果都不满足的话，则k回退，即$k = next[k]$。

为什么是回退到$next[k]$呢？

因为当k需要回退的时候，说明这一位上是匹配失败的。

这时，匹配的最长长度是k-1，我们需要一步步的去回退，直到回退到$k=-1$，重新开始。

那上一步是回退到哪呢，就是长度k-1中前缀和后缀相同的位置，即$next[k-1]$。

也就是将之前的最长长度进行不断的削减。

（有一种递归的感觉

换句话说next数组的意义就是，当第k位匹配失败之后，k需要回退的地方。

优化NEXT数组

当我们计算next数组的时候，会出现一种情况。

就是当这一位匹配成功的时候，他的下一位也是匹配成功的时候。

很显然，在目标串与模式串进行配对的时候，当k指向第二个B时匹配失败的时候，按照我们之前计算的next数组，k是应该回退到第一个B的，但是我们就是因为j指向的那一位与B匹配失败才回退的，这个回退便毫无意义。

所以我们可以对next数组进行优化，当连续两位都相同的时候，便可以跳过这一位。

int next[maxn];

void getnext(string t){
	int j = 0, k = -1;
	int n = t.length();
	while (j < n) {
		if (k == -1 || t[j] == t[k]) {
			j++, k++;
			if (t[j] == t[k])//新增这个判断
				next[j] = next[k];
			else next[j] = k;
		}
		else k = next[k];//k回退
	}
}

匹配方法

在知道next数组时候，便已经了解KMP算法的十之七八了。

接下来只要了解目标串与模式串的比较方法即可。

当我们匹配到这里的时候，从A开始。

显然前三位是相匹配的，j和k指针不断前移。

当匹配到C的时候，不相匹配了，这个时候就需要回退。

根据next数组，B之前最长的前缀长度为1，所以k为1。

然后重新比较C，看是否互相匹配。

直到匹配完成，或者目标串扫描结束。

直接看代码吧。

int next[maxn];

void KMP(string s,string t){
	int j = 0, k = 0;
	int n = s.length(),m = t.length();
	int flag = 0;
	while (j < m && k < n) {
		if (k == -1 || s[j] == t[k])	j++, k++;
		else k = ne[k];
		if (k == n) {//如果k与n相等，则说明存在
			cout << j - n << endl;
			flag = 1;
			break;
		}
	}
	if (!flag) cout << -1 << endl;
}

典型例题

1、ACWing-831 KMP字符串

题目大意

给定一个目标串S，以及一个模式串P，所有字符串中只包含大小写英文字母以及阿拉伯数字。

模式串P在目标串S中多次作为子串出现。

求出模式串P在目标串S中所有出现的位置的起始下标。

解题思路

典型的KMP模板题。

但是需要注意可以重叠。

所以当扫描完成一个之后，$k=next[k]$。

完整代码

#include <iostream>
#include <string>
using namespace std;

const int N = 1e5 + 5;
int ne[N];
string s, t;

int main() {
	int n, m;
	cin >> n >> t >> m >> s;
	ne[0] = -1;
	int j = 0, k = -1;
	while (j < n) {
		if (k == -1 || t[j] == t[k]) {
			j++, k++;
			if (t[j] == t[k])
				ne[j] = ne[k];
			else ne[j] = k;
		}
		else k = ne[k];
	}
	j = 0, k = 0;
	while (j < m && k < n) {
		if (k == -1 || s[j] == t[k])	j++, k++;
		else k = ne[k];
		if (k == n)	k = ne[k], cout << j - n << " ";
	}
}

2、HDU-2087 剪花布条

题目大意

从目标串中寻找模式串的数量。遇到#停止输入。

解题思路

KMP模板题。

但是这个题目不能重叠，和上面那一题不一样。

当扫描出一个时候，需要重新匹配，也就是从剩下的字符串中重新扫描匹配。

完整代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;

const int N = 1010;
int ne[N];
char s[N], t[N];

int main() {
	while (scanf("%s",s)&&strcmp(s,"#")) {
		scanf("%s", t);
		int n, m;
		n = strlen(t);
		m = strlen(s);
		ne[0] = -1;
		int j = 0, k = -1;
		while (j < n) {
			if (k == -1 || t[j] == t[k]) {
				j++, k++;
				if (t[j] == t[k])
					ne[j] = ne[k];
				else ne[j] = k;
			}
			else k = ne[k];
		}
		j = 0, k = 0;
		int ans = 0;
		while (j < m && k < n) {
			if (k == -1 || s[j] == t[k])	j++, k++;
			else k = ne[k];
			if (k == n) {
				ans++;
				k = 0;
			}
		}
		cout << ans << endl;
	}
}