KMP

发表于 | 更新于: | 分类于
字数统计: 2.3k | 阅读时长 ≈ 10

最近学习了一下 KMP 算法，写一下总结，免得忘了。

KMP算法：

暴力匹配的浪费：

假设正在进行下图这样的匹配 :

这里写图片描述

暴力匹配一旦匹配失败，模式串就会回退到开头进行匹配；
我们可以看到，失配字符 ‘C’ 的前两个字符 (AB) 和开头 (AB) 是一样的，如果挪到开头去匹配，很明显会进行一些不必要的匹配；
显然，将箭头所指字符与失配处进行匹配才是 比较 优的。
这里写图片描述

KMP 算法就是基于这个思想的。只要知道有前缀与后缀匹配 的 最大长度，那某个位置失配之后，就能迅速的像上面那样跳到一个 比较 优的位置进行匹配。
为什么是 “比较优” ？后面再说。

什么叫 “前缀和后缀匹配” ?

对于一个位置 $i$ ，如果 $str[0, k - 1] = str[i - k, i - 1] $，那么就说 $i$ 位置前缀匹配后缀的最大长度为 $k$ ；我们用 $Next$ 数组存起来，即 $Next[i] = k$ ；
那么，对 $Next[]$ 下个定义：

$\bullet ; Next[i] : \quad str[0, i - 1]$ 中前缀匹配后缀的最大长度。

如果我们计算出了模式串 $P$ 的每个 $Next[i]$ ，那么在 $pos$ 位置处失配时，立马就可以跳到 $Next[pos]$ 处进行匹配；
所以，$Next$ 数组还可以这样理解：

$\bullet ; Next[i] : \quad$ 当 $i$ 位置失配时应该跳往的匹配位置。

比如上面的模式串 $P$ :

i 0 1 2 3 4 5 6 7
P A B D C A B C ‘\0’
Next -1 0 0 0 0 1 2 0

$\quad i = 0$，对于模式串的首字符，我们统一为 $Next[0] = -1$；
$\quad i = 1$，前面的字符串为 $A$，其最长相同真前后缀长度为 $0$，即 $Next[1] = 0$；
$\quad i = 2$，前面的字符串为 $AB$，其最长相同真前后缀长度为 $0$，即 $Next[2] = 0$；
$\quad i = 3$，前面的字符串为 $ABD$，其最长相同真前后缀长度为 $0$，即 $Next[3] = 0$；
$\quad i = 4$，前面的字符串为 $ABDC$，其最长相同真前后缀长度为 $0$，即 $Next[4] = 0$；
$\quad i = 5$，前面的字符串为 $\color{red}{A}BDC\color{red}{A}$，其最长相同真前后缀为 $A$，即 $Next[5] = 1$；
$\quad i = 6$，前面的字符串为 $\color{red}{AB}DC\color{red}{AB}$，其最长相同真前后缀为 $AB$，即 $Next[6] = 2$；
$\quad i = 7$，前面的字符串为 $ABDCABC$，其最长相同真前后缀长度为 $0$，即 $Next[7] = 0$。

还是开始那个例子，当 $i = 6$ 时，失配，立马就可以跳到 $i = 2$ 的位置进行匹配； faster了有没有？

如何求Next数组?

假设我们现在正在计算 $Next[i]$ ，即之前的 $Next[0, \ldots , i-1]$ 已经得到了；
先上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Get_Next(string P) {
	memset(Next, 0, sizeof(Next));
	int P_len = P.length();
	int i = 0;   //当前枚举的位置
	int p = -1;   //上一次前后缀匹配的最大长度+1,说白了就是Next[i-1]的后一位
	Next[0] = -1;
	while(i < P_len) {
		if(p == -1 || P[i] == P[p]) {
			i++;
			p++;
			Next[i] = p;
		}
		else p = Next[p];
	}
}

代码中最重要的就是那个 if…else… 语句；
一脸懵逼？？？不怕，上图：
这里写图片描述

假设 $i$ 和 $p$ 的位置如上图，上一次前后缀匹配的最大长度为 $p-1$，即绿色的两个椭圆是相等的；
(1) if (P[i] == P[p]) ** ，则往后走就是了；
$\qquad$ p == -1 又是为什么呢？一是 p 初始化为-1，总得往后走吧！二是当前后缀匹配长度为 0 时，p会为-1，这时候也得往后走；
(2) **else
这里写图片描述

由 $Next[p]$ 的定义可知，前两个绿色的椭圆是相等的；于是可知第 $1$ 个和第 $4$ 个椭圆是相等的；
因此，令 $p=Next[p]$ 来加速匹配；

完整代码：

这其实是一道题：HDU-2087

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/**********************************************
 *Author*        :XzzF
 *Created Time*  : 2018/4/26 7:07:32
 *Ended  Time*  : 2018/4/26 12:56:37
*********************************************/

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;
typedef long long LL;
const int inf = 1 << 30;
const LL INF = 1LL << 60;
const int MaxN = 10005;

string S, P;
int Next[MaxN + 5];

void Get_Next(string P) {
	memset(Next, 0, sizeof(Next));
	int P_len = P.length();
	int i = 0;     //当前枚举的位置
	int p = -1;  //上一次前后缀匹配的最大长度+1,说白了就是Next[i-1]的后一位
	Next[0] = -1;
	while(i < P_len) {
		if(p == -1 || P[i] == P[p]) {
			i++;
			p++;
			Next[i] = p;
		}
		else p = Next[p];
	}
}

int KMP(string S, string P) {
	Get_Next(P);
	int i = 0;      //index of S
	int j = 0;      //index of P
	int cnt = 0;
	while(i < S.length() ) {
		if(j == -1 || S[i] == P[j]) {
			i++;
			j++;
		}
		else j = Next[j];
		if(j == P.length()) {
			j = 0;    //不相交匹配则为0,相交匹配则为Next[j]
			cnt++;
		}
	}
	return cnt;
}

int main()
{
	while(cin >> S >> P) {
		if(S[0] == '#') break;
		printf("%d\n", KMP(S, P));
	}
    return 0;
}

KMP优化:

上面还有一个问题没有解决，为什么说 “比较优” ?

问题所在：

其实一开始那个表格就能看到问题了，但还是看个”严重”点的吧！

i 0 1 2 3 4 5 6 7 8 9 10
P A B A C D A B A C E ‘\0’
Next -1 0 0 1 0 0 1 2 3 4 0

假设 $i=8$ 时失配，按照之前的KMP算法，就会把 $p=3$ 处的字符拿过来匹配；然而，这两个字符是相同的，就增加了一些不必要的匹配；
稍微修改一下代码就能解决这个问题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void Get_Nextval(string P) {   //KMP优化
    int P_len = P.size();
    int i = 0;   // P 的下标
    int p = -1;  
    Nextval[0] = -1;

    while (i < P_len)
    {
        if (p == -1 || P[i] == P[p])
        {
            i++;
            p++;
          
            if (P[i] != P[p])
                Nextval[i] = p;
            else
                Nextval[i] = Nextval[p];  //既然相同就继续往前找
        }
        else
            p = Nextval[p];
    }
}
i 0 1 2 3 4 5 6 7 8 9 10
P A B A C D A B A C E ‘\0’
Next -1 0 0 1 0 0 1 2 3 4 0
Nextval -1 0 -1 1 0 -1 0 -1 1 4 0

优化之后，当 $i=8$ 失配时，就能直接跳到 $p=1$ 处匹配，faster 了有没有？匹配方式还是没变的；

严格来讲，未优化的 KMP 算法叫 MP算法；但一般情况下，未优化的 KMP 算法已经够用了；

KMP算法(未优化)： $Next[]$ 表示前后缀匹配的最大长度，还有一些骚操作，后面再说；
KMP算法(优化)： $Nextval[]$ 表示最优长度，但不一定是最长；快是快了，功能少了；

复杂度：$O(n+m)$ 并不会证明

More about KMP :

KMP求最小循环节：

现在假设 $i$ 位置之前的字符串是循环的(比如 $str[0, i-1] = aabaab$) ，我们想求它的最小循环节；

根据 $Next[]$ 的定义，如果 $i$ 位置 相匹配的前后缀没有相互覆盖，显然这个前缀一定不会是循环的，所以我们主要考虑前后缀相互覆盖的情况；

这里写图片描述

如图所示，$Next[i]$ 为红色那段，然后将后面剩下的那段黑色的定义为 $loop$ ，即 $loop = i - Next[i]$；

由于串是在自匹配，所以 $loop$ 是等于后面的两段的；

由 $Next[]$ 定义可知，前两段绿线隔出来的串是相等的，后两段绿线隔出来的串也是相等的；

那我们把前后两段都砍了；

这里写图片描述

这和上面的是一样的嘛！继续砍。。。

这里写图片描述

砍到最后，剩下的 $4$ 个串都是相等的；自然就可以推出上一次砍掉的 $4$ 个串也是相等的；

有点类似于递归回溯的思想；

那么，就说明 $loop$ 就是 $i$ 以前的前缀的 循环节；

再来说为什么是最小的？很简单，

$Next[]$ 的定义是什么？前后缀匹配的 最大 长度！显然，剩下的 $loop$ 就是最小的啦！

既然我们能将每个位置以前的最小循环节求出，那整个串的最小循环节自然就不是问题了；

有一道题可以做一下：HDU-1358

题意就是让从小到大输出哪些位置之前的串是循环的，以及循环次数；

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/********************************************
 *Author*        :XzzF
 *Created Time*  : 2018年04月25日 星期三 21时06分25秒
 * Ended  Time*  : 2018年04月25日 星期三 21时31分56秒
*********************************************/

#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;
typedef long long LL;
const int inf = 1 << 30;
const LL INF = 1LL << 60;
const int MaxN = 1000000;

int n;
string S;
int Next[MaxN + 5];

void GetNext(string S) {
	memset(Next, 0, sizeof(Next));
	int len = S.length();
	int i = 0;
	int pos = -1;
	Next[0] = -1;
	while(i < len) {
		if(pos == -1 || S[pos] == S[i]) {
			i++;
			pos++;
			Next[i] = pos;
		}
		else pos = Next[pos];
	}
}

int main()
{
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int Cas = 0;
	while(cin >> n) {
		if(n == 0) break;
		cin >> S;
		GetNext(S);
		cout << "Test case #" << ++Cas << endl;
		for(int i = 1; i <= n; i++) {
			int loop = i - Next[i];
			//i % loop == 0: 得被长度整除才有可能是循环节吧!
			//i != loop: Next[i]==0时也能满足前一个条件,得判掉
			if(i % loop == 0 && i != loop) 
				cout << i << " " << i / loop << endl;
			//i / loop 就是循环次数了
		}
		cout << endl;
	}
    return 0;
}
------ The happy endingThank you for reading ------
坚持原创技术分享，您的支持将鼓励我继续创作！