YuriCode
0%

KMP

发表于 更新于 分类于
本文字数： 1.9k 阅读时长 ≈ 2 分钟

KMP

KMP（Knuth-Morris-Pratt）算法是一种经典的字符串匹配算法，由 Donald Knuth、James H. Morris 和 Vaughan Pratt 于1977年提出。它在主串和模式串匹配过程中，通过预处理模式串来减少重复匹配的工作，从而显著提高效率

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
int KMP(string s1, string s2)
{
	//s1中比对的位置是x
	//s2中比对的位置是y
	int n = s1.size(), m = s2.size(), x = 0, y = 0;
	vector<int> ne(m);
	ne[0] = -1;
	//i表示当前要求的next的位置
	//cn表示当前要和前一个字符比对的下标
	int i = 2, cn = 0;
	while (i < m) {
		if (s2[i - 1] == s2[cn]) {
			ne[i++] = ++cn;
		} else if (cn > 0) {
			cn = ne[cn];
		} else {
			ne[i++] = 0;
		}
	}
	while (x < n && y < m) {
		//如果相等那么一起++去下一个位置
		if (s1[x] == s2[y]) {
			x++;
			y++;
		//无法往前跳，那么x++到s1的下一个比对位置
		} else if (y == 0) {
			x++;
		//还能往前跳
		} else {
			y = ne[y];
		}
 	}
	return y == m ? x - y : -1;
}
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
   //next数组
   //不含当前，前面字符串前后缀最大匹配长度（不能整体）
   // a  a  b  a  a  b  s  a  a  b  a  a  a  x(终止位置 )
   // 0  1  2  3  4  5  6  7  8  9  10 11 12 13
//-1  0  1  0  1  2  3  0  1  2  3  4  5  2
//next数组有两个含义，一个是基础定义
//另一个代表着这个前缀的再下一个字符所在位置

//S2(较小的那个字符串)
// a  a  b  a  a  b  c  a  a  b  a  a  b  t  ...
// 0  1  2  3  4  5  6  7  8  9  10 11 12 13
//next数组
//-1  0  1  0  1  2  3  0  1  2  3  4  5  6

//S1(较大的那个字符串)
// a  a  b  a  a  b  c  a  a  b  a  a  b  a  ...
// 0  1  2  3  4  5  6  7  8  9  10 11 12 13
//S2(较小的那个字符串)
// a  a  b  a  a  b  c  a  a  b  a  a  b  t  ...
// 0  1  2  3  4  5  6  7  8  9  10 11 12 13

//我们让S2与S1一一比对，在13位置的时候不同，说明S2以0开头不能与S1匹配
//如果使用暴力做法，我们会把S2向右移动1个位置，然后与S1一一比对
//这种方法的时间复杂度是O(n * m)，我们实际上可以用next数组优化S2比对的位置
//将时间复杂度优化到O(n + m)
//此处先给出结论，我们只需要从S1和S2在比对到不同时的位置所对应的next数组开始比对就可以了

///S1(较大的那个字符串)
// a  a  b  a  a  b  c（a  a  b  a  a  b) a  ...
// 0  1  2  3  4  5  6  7  8  9  10 11 12 13
//S2(较小的那个字符串)
//(a  a  b  a  a  b) c (a  a  b  a  a  b) t  ...
// 0  1  2  3  4  5  6  7  8  9  10 11 12 13
//S2(较小的那个字符串)
				   	 //(a  a  b  a  a  b) c  ...
					 // 0  1  2  3  4  5  6

						      // a  a  b  a  ...
						 	  // 0  1  2  3  	


//可以证明，有了next数组那么就可以说明以1 2 3 4 5 6开头必然无法匹配到S2
//同时由于next数组的定义，7 8 9 10 11 12位置已经一一匹配成功，所以接下来只需要看13位置
//具体来说就是因为next数组还可以代表前缀的再下一个字符所在位置
//也就是说这个位置之前的就是前缀
//用数学方法来证明就是我们可以可以把上面带括号的字符串分别设为A, B, C, D
//我们有 D = B = C 且 A = C 那么可以推出 A = D
//这样就证明了为什么7 8 9 10 11 12的位置是相等的
//接下来用反证法证明1 2 3 4 5 6位置不可以
//依据设A, B, C, D的方法来设A', B', C', D'
//假设这样的位置可以匹配，那么A' = D'
//由已知条件A' = C'， B' = D'
//那么推出B' = C'
//根据题设B' > B， 这与next数组矛盾，故假设不成立

   //类似的理解方法，我们可以求出next数组