当前位置:C++技术网 > 资讯 > 深度解析KMP算法

深度解析KMP算法

更新时间:2015-10-26 16:25:05浏览次数:1+次

现在,我已经搞清楚了这个算法并能对它解释。对于那些和我有一样想法的人,下面是我自己的理解。一方面,我不打算解释为什么它比朴素的字符串匹配效率更高;这些在很多地方都已经解释得非常好了。我要说明的是,它究竟是如何工作的。

部分匹配表

毫无疑问,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”的话,我们的部分匹配表应该是这样的:

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 |

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

         bacbababaabcbab

          |

          abababca

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

         bacbababaabcbab

                |||||

                abababca

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)个字符:

         // x 表示一个跳过

bacbababaabcbab

      xx|||

         abababca

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)个字符:

// x 表示一个跳过

bacbababaabcbab

          xx|

             abababca

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

结语

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