KMP算法:线性时间O(n)字符串匹配算法

我在拜读阮一峰老师的这篇文章《字符串匹配的KMP算法》时,最大收获当属手动求部分匹配表的这个例子,(我把它搬过来了,大伙感受一下)——字符串为 $P=ABCDABD$。

字符串 前缀 后缀 部分匹配表
A NULL NULL NEXT[0]=0
AB A B NEXT[1]=0
ABC A, AB BC, C NEXT[2]=0
ABCD A, AB, ABC BCD, CD, D NEXT[3]=0
ABCDA A, AB, ABC, ABCD BCDA, CDA, DA, A NEXT[4]=1
ABCDAB A, AB, ABC, ABCD, ABCDA BCDAB, CDAB, DAB, AB, B NEXT[5]=2
ABCDABD A, AB, ABC, ABCD, ABCDA, ABCDAB BCDABD, CDABD, DABD, ABD, BD, D NEXT[6]=0

(阮一峰老师的这篇文章,基本上是国内网上讲解KMP算法的开山之作了。其特点简短精悍,又能快速让你明白什么KMP算法、什么是部分匹配表)

此时,你应该可以根据前、后缀的概念,手动求出部分匹配表NEXT[*]。不妨试试下面这个例子(该例子摘自《算法导论》)——字符串 $P=ababaca$。
在这里插入图片描述
其中,q表示索引号,string表示字符串,next[7]则为字符串对应的部分匹配表。你的结果与上述表格中的一样吗?

问题1:你可能对NEXT[0]=-1? or 0有所疑惑!

《算法导论》一书上由于下标是从1开始,所以书中NEXT[*]存放的内容为前缀的长度(也同样是下标),而计算机程序下标一般是从0开始,那么长度与下标就相差了一个1。下文为了与《算法导论》一致,也采用了长度(非下标)的存储方式,也就是说部分匹配表中不会出现-1类似的字眼(因为前缀长度>=0)。但这样做是值得的,至少NEXT[*]与《算法导论》一致,也与考试答案一致。

(我看到网上流传的相关KMP文章,NEXT[*]各有不同。本文的举例来自于《算法导论》一书,且我无一字更改,所以例子的正确性能得到保证)

1 KMP算法

问题2:OK,部分匹配表NEXT[*]已经有了。那么,如何利用部分匹配表在必要时快速滑动呢?

举个例子,假设$T=(…bacbababaabcab…)$为一个很长的字符串(以下为截断部分),$P=(ababaca)$为一个较短的被搜索的字符串。

下图中在P[5]处出现了不匹配情况。此时,我们希望P字符串快速向右滑动…要滑动到什么位置呢?

(注意,失配位置必须使用字符串P来描述,因为要滑动的是它,NEXT[*]也是针对它的)
在这里插入图片描述
也就是滑动到,(此刻) $P=(aba’ba)$的前缀与 $T=(…bacbab’aba)$的后缀匹配处
在这里插入图片描述

问题:3: 为什么可以这么滑动?

我们可以将字符串P视为这样的结构“[([前缀,中间,后缀]),剩余部分]”,其中恒有 ([前缀]==[后缀])

举个例子,假设有字符串S=(abcdddabcfg...),那么可以划分为[([abc, ddd, abc]),fg...]。

可以用下面这个图来抽象一下问题,
在这里插入图片描述
(上图是一种简化的画法。因为,前、后缀很多时候是相互杂糅的。拿ababca举例,前缀(aba)baca,后缀ab(abc)a。然而,我们并不需要关心这些细节——我们只需要滑动、对齐)

那么,当在后缀 之后 位置出现不匹配时(暗示着,此时TP两字符串的前面部分全匹配——都为[前缀,中间,后缀]),立即将P串的前缀滑动到与后缀重合的位置,如P'所示,继续开始后续的匹配。

问题4:问题3的前提是,恒有 ([前缀]==[后缀])?这个如何保证?也就是怎么确定后缀之后发生失配时,此时的前缀尾部在哪里?

正好,字符串P的部分匹配表NEXT[*]就是用来回答这个问题的(它里面存放的就是前缀尾部 位置)。

如果将value=NEXT[key]视作一个Map<key, value>结构,其中key指向的是“后缀”的尾部,value指向的就是“前缀”的尾部。(也可以看成 前缀尾部=NEXT[后缀尾部]
在这里插入图片描述
(《算法导论》一书上,失配位置使用T[q]!=P[k]表示,所以上图中的key=q-1value=k-1则为匹配的尾部)

所以能理解“情况2”失配时的做法了吧?它就要根据此刻“失配”的位置(后缀尾部的“下一位”,记为q),从NEXT[*]中取出对应前缀的“长度”(value),再将前缀滑动过来与后缀对齐,继续后续匹配工作….

这个问题回答完毕。

2 部分匹配表

问题5:那么问题4中的,部分匹配表NEXT[*]到底是如何求出来的?

它就是用上文中阮一峰老师的方法求出来的——手动前、后缀表格计算方法(记为手动法)。好吧,虽然事实就是这样,但是在此处我如果这么回答,那是相当的不负责任的说法。

是的,本文末尾(拉到最底部)我还提到了另一个方法(应付考试的方法)。细心的人就会发现,其实“应付考试法”就是用 程序来模拟 前、后缀表格计算方法(记为程序法)。

不信,你继续看。(还是以《算法导论》上的经典字符串P=ababaca为例)

来吧!NEXT[0]是最容易的。 手动法说: “当只有一个字母a的时候它没有前、后缀”。所以程序法初始化时,将NEXT[0]=0
在这里插入图片描述
热身!开始求NEXT[1] 此时已经有两个字母ab了。如果手动计算的话,此时前缀为a,后缀为b,相同的前后缀长度为0,所以NEXT[1]=0

那么,程序法应该怎么做呢?手动法既然要将字符串ab自己的前缀与后缀作比较?那么,我将字符串ab复制成2份,记为nTnP(如下表),并nP向右滑动1格,不就能比较前、后缀了吗?看黄色背景部分,很显然,前、后缀不相等(b!=a),故NEXT[1]=0
在这里插入图片描述
继续!NEXT[2]会不会让我们眼前一亮呢? 此时字符串为aba。还是先分析手动法,前缀为aab,后缀为baa,出现了相同的前、后缀a了,长度为strlen("a")=1。于是有NEXT[2]=1

程序法,还是先复制一份。这里字符串牵涉到多位,为了区分开我设了两个变量qk分别表示这两份字符串的的下标。现在开始将nP向右滑动,当nT[q=2]nP[k=0]时,出现了前、后缀匹配成功,字母为a,长度为1,记NEXT[2]=1
在这里插入图片描述
再来!求NEXT[3]我们将加快效率。 此时字符串为abab,手动法求得前、后缀相同部分为ab,长度为2,故NEXT[3]=2

程序法,我们得加快效率了,每次都从头开始滑动字符串太慢了。因为从上一步我们已经知道了,当字符串为aba时,一路滑动过来,直到最后一位才匹配上。这里没必要做重复工作了,直接比较nT[q=3]?=nP[k=1]即可,唔…相等了。在上一步基础上+1,那么NEXT[3]=1+1=2
在这里插入图片描述
加油!NEXT[4] 我隐约感受到动态规划的味道了。 这里我想已经没有必要再浪费文字讲如何计算它了,在此处,我要讲的是另外一个问题。让我们回到文章开头处,体会下当字符串TPP[5]处失配的那一刻,出现的惊艳一滑。
在这里插入图片描述
OK,当前正在进行上文中NEXT[4]计算阶段,NEXT[4]=3已经被计算出来了。
在这里插入图片描述
此时,NEXT[4]记录的是字符串ababa前、后缀的匹配长度($k’=3$)。好了,根据上文的“[([前缀,中间,后缀]),剩余部分]”,此时后缀最后一个字符为nT[4],我们需要将其对应的前缀滑动过来与后缀对齐。滑动的距离,就是前缀尾部nP[k=2]到后缀尾部nT[q=4]的距离。这里注意两个细节,NEXT[*]存放的是前缀“长度”,失配处是后缀尾部的“下一位”,所以滑动距离计算公式:
$$s’=s+(q-next[q-1])$$所以,$s’=s+(5-next[4])=s+2$,也就是将字符串P迅速向右滑动2个格子。

(请注意甄别,此处我是将KMP匹配、NEXT数组两者混合在一起讲了,请始终把握住我们要滑动的是谁?是的,对于KMP匹配来说是要滑动P,而NEXT数组是要滑动nP

话有点多了….

难点!那么,NEXT[5]=? 这个有点难度。(还是看NEXT[4]的那张图)匹配nT[q=5]?=nP[k=3]时,失配了…怎么办?

回想想KMP算法匹配失败时怎么办?唔…我记得它会根据此刻“失配”时的位置,从value=NEXT[key]中取出对应前缀的“长度”,然后根据上文的公式,将前缀滑动过来与后缀对齐,继续后续匹配工作…(注意,后缀尾部(key)=失配位置-1)

程序法求NEXT[*]的过程中,我们不是一直在做两个字符串匹配的事情么?

那….求NEXT[5]时,不也可以这样处理吗?因为,此时它需要的NEXT[0..4]已经有了。(提示,假设在nP[3]处失配,即k=3,那么后缀尾部应该是2=k-1

引用《算法导论》一书中的一句话,我认为说的非常透彻:“这两个程序有很多相似之处,因为它们都是一个字符串对模式P的匹配:KMP-MATCHER是文本T针对模式P的匹配,COMPUTE-PREFIX是模式P针对自己的匹配。

是不是觉得这里少了张图?唔…因为我把这个例子的图放在下文了,用来解释另一个问题 “递归”

3 算法实现及分析

本文代码与《算法导论》一书基本一致,但是鉴于书上下标是从1开始的,不太符合C++程序的风格。这里参考了c_cloud的《【经典算法】——KMP,深入讲解next数组的求解》一文,将下标改为从0开始(但是NEXT[*]内容仍存储为长度,与应付考试一致)。以下为KMP-MATCHER子程序(简单说明下kmp_matcher子程序的工作原理。以下主要分为三种情况讨论):

int kmp_matcher(const string& t, const string& p) {
int lt = t.size(), lp = p.size();
vector<int> next = compute_prefix(p);
for (int i = 0, q = 0; i < lt; ++i) {
while (q > 0 && p[q] != t[i]) {
q = next[q-1];
}
if (p[q] == t[i]) {
++q;
}
if (q == lp) {
return i - lp + 1;
}
}
return -1;
}

其一, 如果字符串TP当前位情况为匹配,那就直接看下一位是否匹配….,如果匹配长度达到了字符串P的总长度,那么匹配成功,返回(结束)。

其二, 如果字符串TP当前位情况为不匹配“[([前缀,中间,后缀]),剩余部分]”,那么就要根据此刻“失配”时的位置(即,后缀的下一位),从NEXT[*]中取出对应前缀的“长度”,然后根据上文的公式,将前缀滑动过来与后缀对齐,继续后续匹配工作….如再次不匹配,则将“前缀”(后缀,此时都一样)部分再划分为“[(前缀,中间,后缀)]”(见下图,放大镜),再…重复…

(注意,此过程是递归进行的,递归出口为“其一”或“其三”)。
在这里插入图片描述
举个例子,以求NEXT[5]=?为例(此时,在nP[3]处失配)体验一下递归value=NEXT[key]的感受:(再次强调两点)
1、这里失配位置为3不是5,我们始终也必须是以“要滑动的字符串”为位置基准。
2、后缀尾部(key)=失配位置-1。
在这里插入图片描述
其三,(可以看做其二的一个特例)如果字符串T与字符串P的第1位(也就是P[0])就失配了。此时就不要进行“其二”的步骤了,而应该将字符串T的下一位与P[0]进行匹配。

好了,KMP匹配算法告一段落……

以下为部分匹配表生成子程序COMPUTE-PREFIX(这里我不再说明这部分程序了)。

//部分匹配表NEXT[]
std::vector<int> compute_prefix(const string& p) {
int lp = p.size(), k = 0;
std::vector<int> next(lp, 0);//next[0] = 0
for (int q = 1; q < lp; ++q) {
while (k > 0 && p[k] != p[q]) {
k = next[k-1];
}
if (p[k] == p[q]) {
++k;
}
next[q] = k;
}
return next;
}

4 手动快速计算部分匹配表

如果只是为了应付考试,想知道如何快速求部分匹配表NEXT[*](又觉得上述手动法枚举前、后缀表格方式太耽误时间)的小伙伴,我这里再介绍一种方式。

计算NEXT[*]时,首先将NEXT[0]=0,然后再将问题分为匹配时和失配时2种情况讨论:

1种情况为匹配时(以求NEXT[3]=?为例)
在这里插入图片描述
根据上图,此时str[3]?=str[next[3-1]]。相等,那么,NEXT[3]=NEXT[3-1]+1=2

2种情况为失配时(以求NEXT[5]=?为例)
在这里插入图片描述
根据情况1,首先比较str[5]?=str[next[5-1]]。不相等(也就是失配),这时候,应该比较str[5]?=str[next[next[5-1]]],也就是str[5]?=str[2]。又不相等,再比较str[5]?=str[1]。还是不相等,但是此时取出的NEXT[1]==0,表示应该终止,同时将NEXT[5]=0。(注意,在此过程中一旦某一步出现了相等,那么立即转为第1种情况)

本文也印证了知乎上流传已久的那句老话:“等你的能力足够理解后缀数组时,你就能明白KMP算法了”。

References:
[1] Thomas H.Cormen 《算法导论》 588页~594页
[2] 阮一峰的《字符串匹配的KMP算法》,2018-12-27
[3] c_cloud的《【经典算法】——KMP,深入讲解next数组的求解》,2018-12-27