经典算法:第一讲 字符串匹配算法入门——KMP遍历算法

本文最后更新于:10 个月前

如何在一串字符串中高效的匹配到我们想找的字符串的位置?比如abcd中bc在哪个位置?

暴力匹配算法

假设我们有一个长字符串S:[BBCABCDABABCDABCDABDE]和短字符串P:[ABCDABD]
我们最容易想到的算法就是直接对字符串直接遍历,然后使用滑动匹配的方法一个一个进行比对。

text
首先让S[0]和P[0]进行比对,A!=B,所以匹配失败

text
再让S[1]和P[0]进行比对,依然失败,继续滑动

text
然后到S[5]和P[0]匹配成功,则让S[6]和P[1]相匹配,直到P被匹配完或者匹配失败为止。

text
直到S[10]遇到空格匹配失败,然后又继续从S[6]往后重新开始匹配。

至此,我们可以看到,如果按照暴力匹配算法的思路,尽管之前文本串和模式串已经分别匹配到了S[9]、P[5],但因为S[10]跟P[6]不匹配,所以文本串回溯到S[5],模式串回溯到P[0],从而让S[5]跟P[0]匹配。

这个时候,同学们思考一下,我们在S[10]匹配失败的时候有没有必要再回退到S[6]去?很显然,是没有必要的,为什么?

因为我们可以清楚的看到,回退回去肯定是匹配失败的,所以我们应该回退到哪个点?
或者说我们可不可以设计一个算法使得P序列在匹配失败后,可以继续向前走k格。

这个匹配算法就叫做KMP算法,它可以使得我们的P序列每一个值都有一个相匹配的移动格数。

KMP算法

所以我们只需要计算一个与P相对应的next[]数组,然后每到一个匹配失败的字符处,就向前移动next[j]格,这样,我们就可以很快的匹配完S序列。

text
继续拿之前的例子来说,当S[10]跟P[6]匹配失败时,KMP不是跟暴力匹配那样简单的把模式串右移一位,而是执行第②条指令:“如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j]”,即j 从6变到2(后面我们将求得P[6],即字符D对应的next 值为2),所以相当于模式串向右移动的位数为j - next[j](j - next[j] = 6-2 = 4)。

text
向右移动4位后,S[10]跟P[2]继续匹配。为什么要向右移动4位呢,因为移动4位后,模式串中又有个“AB”可以继续跟S[8]S[9]对应着,从而不用让i 回溯。相当于在除去字符D的模式串子串中寻找相同的前缀和后缀,然后根据前缀后缀求出next 数组,最后基于next 数组进行匹配。

算法步骤

寻找前缀后缀最长公共元素长度

对于P = p0 p1 …pj-1 pj,寻找模式串P中长度最大且相等的前缀和后缀。如果存在p0 p1 …pk-1 pk = pj- k pj-k+1…pj-1 pj,那么在包含pj的模式串中有最大长度为k+1的相同前缀后缀。举个例子,如果给定的模式串为“abab”,那么它的各个子串的前缀后缀的公共元素的最大长度如下表格所示:
text
比如对于字符串aba来说,它有长度为1的相同前缀后缀a;而对于字符串abab来说,它有长度为2的相同前缀后缀ab(相同前缀后缀的长度为k + 1,k + 1 = 2)。

求next数组

next 数组考虑的是除当前字符外的最长相同前缀后缀,所以通过第①步骤求得各个前缀后缀的公共元素的最大长度后,只要稍作变形即可:将第①步骤中求得的值整体右移一位,然后初值赋为-1,如下表格所示:
text
比如对于aba来说,第3个字符a之前的字符串ab中有长度为0的相同前缀后缀,所以第3个字符a对应的next值为0;而对于abab来说,第4个字符b之前的字符串aba中有长度为1的相同前缀后缀a,所以第4个字符b对应的next值为1(相同前缀后缀的长度为k,k = 1)。

根据next数组进行匹配

匹配失配,j = next [j],模式串向右移动的位数为:j - next[j]。换言之,当模式串的后缀pj-k pj-k+1, …, pj-1 跟文本串si-k si-k+1, …, si-1匹配成功,但pj 跟si匹配失败时,因为next[j] = k,相当于在不包含pj的模式串中有最大长度为k 的相同前缀后缀,即p0 p1 …pk-1 = pj-k pj-k+1…pj-1,故令j = next[j],从而让模式串右移j - next[j] 位,使得模式串的前缀p0 p1, …, pk-1对应着文本串 si-k si-k+1, …, si-1,而后让pk 跟si 继续匹配。如下图所示:
text
综上,KMP的next 数组相当于告诉我们:当模式串中的某个字符跟文本串中的某个字符匹配失配时,模式串下一步应该跳到哪个位置。如模式串中在j 处的字符跟文本串在i 处的字符匹配失配时,下一步用next [j] 处的字符继续跟文本串i 处的字符匹配,相当于模式串向右移动 j - next[j] 位。

总的来说,这个算法的主要思想就是在遍历之前,我就知道在哪个字符匹配失败之后,应该向前走多少格。

那么,问题又来了,也许你会发现,好像KMP的效率并不是很高,那么我们有没有更加高效的算法应用在字符串的匹配中呢?

Sunday算法

这个算法也是非常的简单粗暴,就是直接不管后面是什么字符,只关注最后一个字符,只关注字符串最后一个的下一个字符。
举个例子:
刚开始时,把P串与S串左边对齐:
substring searching algorithm
search
^
然后匹配不成功,直接跳到下一个字符i,由于i不在S串中,所以直接从i的下一个n开始,然后
substring searching algorithm
    search
     ^
这个时候第一个字符也不匹配,然后直接看下一个字符r,我们发现r在P串中出现,就是P[3],所以我们直接将P[3]与刚才的S串中的r对齐,那么
substring searching algorithm
     search
        ^
匹配成功,就是这么快。由于每一步都会移动的非常快,所以这个算法的效率非常高。

有不懂的地方请留言评论。