KMP

开始 Starting

此篇文字谨以记录关于KMP算法,必须写点什么巩固自己的印象

题目:https://leetcode-cn.com/problems/implement-strstr/

题目 Question

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

想法 Thinking

一开始想用Brutal-force, 然不知为何python写的brutal force 竟然超时了。。。看题解发现有一个铭文KMP 的算法,遂再搜索一番,好好学习了一下

算法 Algorithm

首先暴力:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
i = 0
if needle == '':
return 0
while i < len(haystack):
if haystack[i:i+len(needle)] == needle:
return i
else:
i+=1

return -1

这里强烈推荐本视频https://www.youtube.com/watch?v=dgPabAsTFa8

配合这篇回答,https://www.zhihu.com/question/21923021,对KMP会有很好的理解

KMP算法主要包含两个主体:

  1. 由Partial Match Table 加以更改得到的Next table (prefix table)
  2. 调用Next table 的KMP 算法

Next table

前后缀

举个:chestnut:子:

”Harry”的前缀包括{”H”, ”Ha”, ”Har”, ”Harr”}

”Potter”的后缀包括{”otter”, ”tter”, ”ter”, ”er”, ”r”}

Note: 字符串本身并不是自己的前后缀。

PMT

Partial Match Table (PMT) 中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度.

例如,对于”aba”,它的前缀集合为{”a”, ”ab”},后缀 集合为{”ba”, ”a”}。两个集合的交集为{”a”},那么长度最长的元素就是字符串”a”了,长 度为1,所以对于”aba”而言,它在PMT表中对应的值就是1。再比如,对于字符串”ababa”,它的前缀集合为{”a”, ”ab”, ”aba”, ”abab”},它的后缀集合为{”baba”, ”aba”, ”ba”, ”a”}, 两个集合的交集为{”a”, ”aba”},其中最长的元素为”aba”,长度为3。

如图 1.12 所示,要在主字符串”ababababca”中查找模式字符串”abababca”。如果在 len 处字符不匹配,那么由于前边所说的模式字符串 PMT 的性质,主字符串中 i 指针之前的 PMT[len −1] 位就一定与模式字符串的第 0 位至第 PMT[len−1] 位是相同的。这是因为主字符串在 i 位失配,也就意味着主字符串从 i−len 到 i 这一段是与模式字符串的 0 到 len 这一段是完全相同的。而我们上面也解释了,模式字符串从 0 到 len−1 ,在这个例子中就是”ababab”,其前缀集合与后缀集合的交集的最长元素为”abab”, 长度为4。所以就可以断言,主字符串中i指针之前的 4 位一定与模式字符串的第0位至第 4 位是相同的,即长度为 4 的后缀与前缀相同。这样一来,我们就可以将这些字符段的比较省略掉。具体的做法是,保持i指针不动,然后将len指针指向模式字符串的PMT[len −1]位即可。

简而言之,首先进行普通匹配,发现在i,j处失配,因为PMT 的性质,我们知道模式字符串前6位的最长前后缀交集长度为4,因为模式字符串前j-1位都是匹配的,那么也就是说主字符串的后缀能够和模式字符串的前缀匹配上。 那么自然而然的,图(a) 的灰色部分就不需要匹配了。相当于

图片在回答中查看

Next Table

next table 就是把pmt 给右移了,并且在第0个位置变成了 -1

图片在回答中查看

如何创建 next table

首先我们可以发现一个规律:如果列举出所有模式字符串的substring:

1
2
3
4
5
6
7
8
9
10
# Given: P= ABABCABA
# All possible substrings in a list :
A # substrings[0] next table: 0
AB # substrings[1] next table: 0
ABA # substrings[2] next table: 1
ABAB # substrings[3] next table: 2
ABABC # substrings[4] next table: 0
ABABCA # substrings[5] next table: 1
ABABCAB # substrings[6] next table: 2
ABABCABA # substrings[7] next table: 3

如果已知某一个substrings[i] 的pmt 值,想得到 substrings[ i+1 ]的pmt 值,我们发现如果substrings[i+1] 的最后一位如果等于 在substrings[i] 的pmt值 所对应的那一位(把这个pmt当成index),那么 substrings[ i+1 ]的pmt 值 等于substrings[i] 的pmt值+1。

也就是说,对于某个next table 中的值(称为 next),我们可以理解为包含当前字母的substring 的最长公共前后缀的大小,也可以表明当前substring 的第next-1 位字母和为最长公共前后缀的最后一个字母

栗子就是上面ABABCA 的pmt 是1,如果B == P[ABABCAB的pmt] 可以得到ABABCAB的pmt+1。

如果不相等,我们则回溯到len=next[len-1]。我们并非是在斜着对,目的是找到之前最长prefix里面的最长prefix是多少,从而判断最后加进来的那个字符可能组成为多长的新的prefix。例如 p = aaabaaaa这个例子,当倒数第一个a ,i=7, len=3, 首先a不等于b, 所以我们排除b,考虑 len= next[2] = 2 。记住,next表示的是最大前后缀, 即aa为最大前后缀,此时p[i] == p[2] ,即next[i] = len+1!

这种创建方法可以参考上面贴的油管链接。

根据原理我们可以得到next:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def getNext(pattern: str) -> List[int]:
next = [None] * len(pattern)
next[0] = 0
i = 1 # start from next[1]
len = 0
while i < len(pattern):
if pattern[i] == pattern[len]: #next[1] = 0
len+=1
next[i] = len
i+=1
else:
if len>0:
len = next[len-1] #回溯到上一个
else:
next[i] = len # =0
i+=1
# Right shift 1
i = len(next)-1
while i > 0:
next[i] = next[i-1]
i-=1
next[0] = -1
return next

或者有种简单的想法:

其实,求next数组的过程完全可以看成字符串匹配的过程,即以模式字符串为主字符串,以模式字符串的前缀为目标字符串,一旦字符串匹配成功,那么当前的next值就是匹配成功的字符串的长度。

具体来说,就是从模式字符串的第一位(注意,不包括第0位)开始对自身进行匹配运算。 在任一位置,能匹配的最长长度就是当前位置的next值。

Note: next 的第一位是被shift 得到的,一定为-1,第二位因为是求得于长度仅为1 的substring, 必定此next 值为0。最后一位会被shift掉,所以也不用care\

总代码:

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
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if needle == "":
return 0

next = self.next_table(needle)
i = 0 # for haystack
j = 0 # for needle
while i < len(haystack):
if j == len(needle) -1 and haystack[i] == needle[j]:
return i-j
if haystack[i] == needle[j]:
i += 1
j += 1
else:
j = next[j]
if j == -1:
i += 1
j += 1
return -1



def next_table(self, arr):
next = [None] * len(arr)
next[0] = 0
# i represents the substring [0:i]
i = 1
# j represents the possible next value
j = 0
while i < len(arr):
if arr[i] == arr[j]:
j+=1
next[i] = j
i+=1
else:
if j > 0:
j = next[j-1]
else:
next[i] = j
i+=1
# right shift
i = len(next) - 1
while i >= 0:
next[i] =next[i-1]
i-=1
next[0] = -1
return next

运行时间 Run-time

暴力算法 O(mn)

KMP算法 O(m+n)

反思 Introspection

需要多次复习加深印象

对于 getNext 的细节,需要多加复习


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!