Ea5ter's Bolg

KMP算法

字数统计: 1.1k阅读时长: 4 min
2018/09/08 Share

开始是在 Lintcode 看到的一道题。

一开始的思路是这样的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def strStr(self, source, target):
i = 0
j = 0
k = 0
while i < len(source):
if source[k] == target[j]:
k += 1
j += 1
if j == len(target) - 1:
return 1
else:
j = 0
i += 1
k = i
return -1

source 有两个指针 i 、k ,i 用来移动,k 用来比较。但这段代码有很多没考虑到的情况,具体的情况这不细述。不过这里提及的 KMP 算法却有点东西。

KMP 算法简介

这个算法是由三个大牛想出来的,用于在主串(T)中查找模式串(P)。
一般想到的查找方式就像我自己写的那样:依次比较,如果匹配 T 和 P 的指针都向后移动一位,若不匹配 T 的指针向后移动一位 P 的指针回到 0 。
这种低效率的方法会遇到很多不友好的情况比如:

1
2
T: 00000000000000dxd
P: 000dxD

这种情况要到最后一位才发现不匹配。
因此 KMP 要解决的一个重要的问题就是,当出现不匹配的情况时,P 的指针要移到哪里?
如下图:P 的指针下一步该移动到哪?

当然应该是移动到 P[1] 处,因为前面的 ‘A’ 已经相等了

当 P[j] 出现不匹配时,就将 P 的指针移动到 k 处。我们设每一个 j 都有一个对应的 k ,因此设置一个数组 next ,使 next[j] = k。我们可以大概写出一个匹配模型:

1
2
3
4
5
6
7
8
while i < len(T):
if T[i] == P[j]: # 如果 T[i] 匹配 P[j] 那么就匹配下一个
i += 1
j += 1
if j == len(P):
return 1
else: # 如果 T[i] 不匹配 P[j] 那么就使 P 的指针回到 next[j] 所对应的 k
j = next[j]

可以看到这种方法比起之前的暴力破解,最大的区别就是 i 不用回溯了。接下来的问题就是解决 next 数组。

next 数组求解

首先要介绍两个概念:前缀、后缀。前缀就是字符串除去最后一个字符前面剩下的字符,后缀反之。
接下来就开始求解 next 数组。

当第一个字符不匹配时,T 应该向右移动,因为 P 已不能向左移动了,所以 next[0] = -1。
接下来的 k 值就会有一个规律:next[j] = next 前 j 个字符的前缀与后缀的最长的子串的字符数。要注意的是:前缀必须要从头开始算,后缀要从最后一个数开始算,中间截一段相同字符串是不行的!

以这串字符为例求 next[j] ,前 j 个字符为“ABCAB”,前缀是“ABCA”,后缀是“BCAB”,前缀与后缀相同的字符数为 2 。所以 next[j] = 2,当 P[j] 匹配失败时,P 的指针也就会移动到 P[2] = C。
接下来通过一个模拟匹配来演示下 next 数组的求解。
初始化 next[0] = -1,开始匹配:

要求 next[1] 比较前 1 个字符 “a”,显然前后缀都为空,相同的字符个数为 0

后移一位,求next[2] ,前缀“a”,后缀“b”,相同 0

继续求 next[3] ,前缀“ab”,后缀“ba”,相同 1

然后

接下来求 next[5] ,但是 c != a 那么 P 该回溯到哪呢?
这里可以类比成 P 和 T 的比较。当 P 匹配错误时,指针回到 next[j]。P[2] 匹配错误,自然就回溯到 next[2]。如果错误就使 k = next[k] 继续回溯,直到匹配成功或 k = -1 终止。其实这种回溯可以用在每一次的匹配上,只要回溯到 k = -1 就可以理解成一种重置。

1
2
3
4
5
6
7
8
9
10
11
12
13
def pnext(self, P):
k = -1
j = 0
pnext = []
pnext.append(-1)
while j < len(P):
if (k == -1 or P[j] == P[k]):
pnext.append(k + 1)
j += 1
k += 1
else:
k = pnext[k]
return pnext

最后把 next 带入主函数就,kmp 算法就基本上实现了。为什么说基本上,因为 next 数组的生成和 T,P 的匹配是可以同时进行的。有兴趣的话可以在网上看下完整代码。

参考文章

KMP算法NEXT数组计算方法
kmp算法next数组求解过程和回溯的含义(tip:评论区很精髓)
(原创)详解KMP算法

CATALOG
  1. 1. KMP 算法简介
  2. 2. next 数组求解
  3. 3. 参考文章