我理解的 KMP 算法

最近一段时间,我一直在看 KMP 字符串模式匹配算法的各种不同解释。因为各种原因,没有找到一种我觉得好的解释。当我读到“……的前缀的后缀的前缀”时,我会不停地拍自己的脑袋

最后,花了大约30分钟将《算法导论》里相同的部分反反复复读了以后,我决定坐下来做一些例子和图解。现在,我已经搞清楚了这个算法并能对它解释。对于那些和我有一样想法的人,下面是我自己的理解。一方面,我不打算解释为什么它比朴素的字符串匹配效率更高;这些在很多地方都已经解释得非常好了。我要说明的是,它究竟是如何工作的。

部分匹配表

毫无疑问,KMP算法的精髓是部分匹配表。我理解KMP算法时,最大的障碍就在于是否充分明白部分匹配表里的值所代表的意义。下面我会尽可能简单地来解释这些。

下面这个是“abababca”这个模板的部分匹配表:

char:   | a | b | a | b | a | b | c | a |

index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |

value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |

如果我有一个8个字符的模板(这里我们就用“abababca”来举例子),我的部分匹配表将会有8格。如果此时此刻我正匹配模板的第8格即最后一格,那意味着我匹配了整个模板(“abababca”);如果我正匹配模板的第7格,则意味着当前仅匹配了整个模板的前7位(“abababc”),此时第8位(“a”)是无关的,不用去管它;如果我此时此刻正匹配模板的第6格,那意味着……看到这里你应该已经明白我的意思了。目前我还没有提到部分匹配表每格数据的含义,在这里仅仅是交代了大概。

现在,为了说明刚刚提到的每格数据的含义,我们首先要明白什么是最优前缀什么是最优后缀

最优前缀:一个字符串中去除一个或多个尾部的字符所得的新字符串就是最优前缀。例如 “S”、 “Sn”、 “Sna”、 “Snap”都是“Snape”的最优前缀。

最优后缀:一个字符串中,去除一个或多个首部的字符所得的新字符串就是最优后缀。例如“agrid”、 “grid”、“rid”、 “id”、“d”都是 “Hagrid”的最优后缀。

有了两个概念,我现在可以用一句话来概括部分匹配表里每列数据的含义了:

模板(子模板)中,既是最优前缀也是最优后缀的最长字符串的长度。

下面我举例说明一下这句话。我们来看部分匹配表的第3格数据,如果你还记得我在前面提到的,这意味着我们目前仅仅关心前3个字母(“aba”)。在“aba”这个子模板中,有两个最优前缀(“a”和“ab”)和两个最优后缀(“a”和“ba”)。其中,最优前缀“ab”并不是最优后缀。因此,最优前缀与最优后缀中,相同的只有“a”。那么,此时此刻既是最优前缀也是最优后缀的最长字符串的长度就是1了。

我们再来试试第4格,我们应该是关注于前4个字母(“abab”)。可以看出,有3个最优前缀(“a”、“ab”、 “aba”)和3个最优后缀(“b”、“ab”、“bab”)。这一次 “ab” 既是最优前缀也是最优后缀,并且长度为2,因此,部分匹配表的第4格值为2。

这是很有趣的例子,我们再看看第5格的情况,也就是考虑“ababa”。我们有4个最优前缀(“a”、 “ab”、“aba”,和“abab”)和4个最优后缀(“a”、 “ba”、“aba”,和“baba”)。现在,有两个匹配“a”和“aba” 既是最优前缀也是最优后缀,而“aba”比“a”要长,所以部分匹配表的第5格值为3。

跳过中间的直接来看第7格,此时只考虑字母“abababc”。即使不一一枚举出所有的最优前缀与最优后缀也不难看出,这两个集合之间不会有任何的交集。因为,所有最优后缀都以“c”结尾,但没有任何最优前缀是以“c”结尾的,所以没有相匹配的,因此第7格值为0。

最后,让我们看看第8格,也就是考虑整个模板(abababca)。它的最优前缀与最有后缀都以“a”开头以“a”结尾,所以第8列的值至少是1。然而1就是最终结果了,所有长度大于等于2的最优后缀都包含“c”,但只有“abababc”这一个最优前缀包含“c”,这个7位的最优后缀“bababca”并不匹配,所以第8列最终赋值为1。

如何使用部分匹配表

当我们找到了部分匹配的字符串时,可以用部分匹配表里的值来跳过前面一些字符(而不是重复进行没有必要的比较)。具体是这样工作的:

如果已经匹配到的部分字符串的长度为partial_match_length且 table[partial_match_length] > 1,那么我们可以跳过partial_match_length- table[partial_match_length – 1]个字符。

比如,我们拿“abababca”来这个模板来匹配文本“ bacbababaabcbab”的话,我们的部分匹配表应该是这样的:

第一次匹配的时候是在这里

partial_match_length值为1,对应的table[partial_match_length – 1] (即table[0])值为0。所以,这种情况下我们不能跳过任何字符。下一次的匹配是这里:

partial_match_length值为5,对应的 table[partial_match_length – 1] (即 table[4])值为3。这意味着我们可以跳过 partial_match_length- table[partial_match_length – 1] (即 5 – table[4]5 – 3 亦即 2)个字符:

partial_match_length值为3,对应的 table[partial_match_length – 1] (即 table[2])值为1,这意味着我们可以跳过 partial_match_length- table[partial_match_length – 1] (即 3- table[2]3 – 1亦即 2)个字符:

现在,模板长度大于所剩余的目标字符串长度,所以我们知道不会再有匹配了。

结语

那么你应该搞明白了吧。就像我一开始说的,这篇文章没有关于KMP多余的解释或者或枯燥的证明;而是我自己的理解,以及我发现的容易让人感到迷惑部分的详尽解释。如果你有任何疑问或者发现我这篇文章哪里写错了,请给我留言;也许我们都会有所收获。

4 16 收藏 3 评论

关于作者:LynnShaw

微博:@萧萧萧宁 个人主页 · 我的文章 · 34

相关文章

可能感兴趣的话题



直接登录
最新评论
跳到底部
返回顶部