数据结构+算法=程序
程序+设计模式=框架

0%

彻底搞懂KMP算法原理

简介

KMP算法是什么?
引用自百度百科:

KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。

也就是说,KMP算法是用来解决字符串匹配问题的,从一个主字符串text中寻找一个子字符串(模式字符串)pattern,看这个子串是否在主串中,比如对于text='abaacababcac'pattern='ababc',子串是包含在主串中的,同时它在主串中的索引是5。

字符串匹配暴力法

一般的字符串匹配解法是将2个串的字符进行挨个比较,相当于是把每个字符都比较了一遍,这样是一定能得到结果的,不过显然这样操作导致的时间复杂度是$ O(m*n) $,也就是2个字符串的长度之积,俗称暴力解法。

用图像表示暴力解法的过程如下:
一开始,i和j分别指向主字符串和子字符串,

这个时候开始比较t[i]p[j],如果匹配则i和j同时向右移动一格,这样i和j同时移动到了位置3,

此时i和j不匹配了,需要对i和j进行回退,i回退到了它最开始的下一位置,即位置1,而j回退到位置0

此时i和j仍然不匹配,i继续向右移动一格,即位置2,j依然保持位置0

如此反复,每当不匹配时,i都会回到开始匹配的位置同时移动一格,而j回到位置0,当匹配时,i和j同时向右移动,直到j到达子字符串的末尾。

代码表示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def strStr(self, text: str, pattern: str) -> int:
n1,n2=len(text),len(pattern)
if n2==0:
return 0
i,j=0,0
while i<n1:
if text[i]==pattern[j]: #相等时同时移动
i+=1
j+=1
else:
i-=j #回到最开始匹配的位置
i+=1 #向右移动一格
j=0 #j回到位置0
if j==n2: #到达字符串末尾,说明匹配成功,返回结果
return i-n2
return -1

KMP算法原理

KMP算法则用了一种聪明的办法,当发现字符串不匹配的时候,并不会从头开始比较,因为之前已经匹配成功的字符可以给我们提供一些有用的信息,利用这个信息我们可以将子串移动到某个位置,并从这个位置直接开始比较,它的时间复杂度降到了$ O(m+n) $,也就是2个字符串的长度之和。

网上有很多关于KMP的代码,大体知道是通过计算子串(模式串)自身来获得一个next数组,然后在匹配过程中通过next数组来决定下一个匹配位置,代码虽然不复杂,然而知其然不知其所以然,如果不明白其中原理,那么很难将这个算法写出来。

本文将介绍一种最朴素的KMP算法,目的就在于彻底搞懂KMP算法原理,它的next是怎么来的,以及算法是如何奏效的。

字符串的前缀和后缀

首先我们需要知道字符串的前缀和后缀:
对于字符串ababc来说,它的前缀有[a,ab,aba,abab],也就是以字符串第一个字符作为开头,同时不包括最后一个字符的所有子串,同理它的后缀有[c,bc,abc,babc],也就是以字符串最后一个字符作为结尾,同时不包括第一个字符的所有字串。

字符串的最长公共前后缀

了解了这个,我们再来说什么是字符串的最长公共前后缀,说白了,也就是前缀和后缀这2个集合中的相同部分,同时取最长的那个,就是这个字符串的最长公共前后缀。显然,在这个例子中,ababc是没有公共前后缀的。但是对于abab,它的前缀和后缀分别是[a,ab,aba][b,ab,bab],那么它的最长公共前后缀就是ab

现在,我们的目标就是取得ababc所有子串[a,ab,aba,abab,ababc]最长公共前后缀的长度,分别保存在next数组中,我们只要知道最大长度即可,并不用关心串具体是什么,而我们目前通过观察即可得出next数组这里是[0,0,1,2,0],我们先知道这个结果即可,此计算方法后续会说明。

KMP的思路分析

得到这个有什么用,回到刚刚的例子,当我们第一次碰到不匹配时(i和j都等于3的时候):

此时i和j之前的3个字符aba必然完全匹配的,因为只有前面匹配成功了j才能走到3,而我们又知道aba最长公共前后缀a,这可以给我们一个很好的提示,主串中的aba的后缀和字串中的aba前缀有最长的公共部分a,这样一来,我们就没必要重新比较了,直接将相同部分对齐就好了,也就是说让j退回到位置1就可以了,而i保持不变。

分析一下,为什么j知道应该退回到位置1:

  1. 我们知道j是在位置3不匹配的,那么j前面的字符串我们可以知道是aba
  2. 前面我们已经得到了next数组,知道aba的最长公共前后缀长度是1
  3. 也就是说,我们可以知道i之前1个位置(主串的后缀)和子串开头之后1个位置(子串的前缀)是相同的
  4. 进而我们可以让相同部分对齐,也就是让j=next[j-1]

接下来,我们发现i和j仍然不匹配,而j之前的字符a最长公共前后缀是0,此时j退到位置0,i仍然保持不变。

i和j匹配,同时右移一格

此时i和j不匹配,j=next[j-1]回退到0,然后我们发现i和j仍然不匹配,同时j已经是0了,那么我们就让i往右移动一格。

可以看到,相比于暴力解法,i始终在前进,并没有后退(顶多保持不变),然后我们通过next数组来改变j的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def strStr(self, text: str, patten: str) -> int:
next=KMP(patten) #获取next数组
n1,n2=len(text),len(patten)
if n2==0:
return 0
i,j=0,0
while i<n1:
if text[i]==patten[j]:
i+=1
j+=1
else:
if j>0:
j=next[j-1]
else:
i+=1
if j==n2:
return i-n2
return -1

求解字符串最长公共前后缀

最后,我们还剩下一个问题,如何求next数组,也就是求模式字符串各个子串的最长公共前后缀长度。
我们先初始化一个和模式字符串长度相等的next数组,在next数组中,第1位默认为0,因为我们规定只有一个字符的字符串没有前缀和后缀,自然公共前后缀长度只能是0。
我们依然设定2个指针i和j,j指向位置0,i从位置1开始依次为next数组进行赋值

我们可以把这个过程依然看作是2个字符串的比较,j指向的是模式字符串的前缀,而i指向的是模式字符串的后缀

和上面的字符串匹配一样,我们执行同样的处理:

  1. 当i和j匹配时,i和j同时右移一格
  2. 当i和j不匹配时,如果j不在字符串开头(位置0),就回退到上一个能匹配到的位置
  3. 当i和j不匹配时,如果j在字符串开头(位置0),那么i就右移一格

对next[1]赋值:i和j不匹配,同时j已经是字符串开头,赋值0

对next[2]赋值,i和j匹配,此时j为0,代表只有1个字符匹配(j+1),赋值1

对next[3]赋值,i和j匹配,此时j为1,代表有2个字符匹配(j+1),赋值2

对next[4]赋值,i和j不匹配,此时j为2,可以得知j前面的字符是ab,而ab的最长公共前后缀长度就是next[1],这个值我们前面已经求得了结果是0,所以j回退到位置0,用代码表示就是j=next[j-1]

此时i和j仍然不匹配,但是j已为0,无法继续回退,所以直接对next[4]赋值为0

实际上,我们在求解模式字符串ababc的最长公共前后缀长度的时候,不可避免的会对它的子串进行求解,这样可以方便在不匹配时进行回退,这也是动态规划的思想,要求的结果可以用先前已经求得的结果得出。而我们本身就是要对模式字符串的各个子串进行求解,所以可谓一举两得。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def KMP(patten):
if not patten:
return []
n=len(patten)
next=[0]*n
i,j=1,0
while i<n:
if patten[i]==patten[j]:
next[i]=j+1
i+=1
j+=1
else:
if j>0:
j=next[j-1]
else:
next[i]=0
i+=1
return next

对比一下上一段的字符串匹配代码,可以发现,2段代码的执行逻辑几乎一模一样,不同之处只是我们在比较过程中插入了对next数组进行赋值的代码。

可以这样理解,在字符串匹配中,i指向的是主串,j指向的子串,比较的是主串和子串。而在求公共前后缀的时候,我们相当于把模式字符串拆成了前后两部分,同样是对这2部分进行字符串匹配,相当于自己比自己。

以上就是KMP算法的核心原理及实现,当然,实现方式并不是只有我这一种,KMP的实现算法多种多样,包括生成的next数组都会不一样,而我这里的代码只是希望能够把KMP的思路表述清楚:

  1. KMP通过计算模式字符串自身得到next数组;
  2. 不匹配时通过next数组信息进行回退,而不用再从头开始比较;
  3. 原理就是利用模式字符串的公共前后缀信息,所以算法是奏效的。
  • 本文作者: XDull
  • 本文链接: https://www.xdull.cn/kmp.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!