| 注册
请输入搜索内容

热门搜索

Java Linux MySQL PHP JavaScript Hibernate jQuery Nginx
jopen
9年前发布

我理解的 KMP 算法

原文  http://blog.jobbole.com/90576/
 

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

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

部分匹配表

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

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

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多余的解释或者或枯燥的证明;而是我自己 的理解,以及 我发现的容易让人感到迷惑部分的详尽解释。如果你有任何疑问或者发现我这篇文章哪里写错了,请给我留言;也许我们都会有所收获。

 本文由用户 jopen 自行上传分享,仅供网友学习交流。所有权归原作者,若您的权利被侵害,请联系管理员。
 转载本站原创文章,请注明出处,并保留原始链接、图片水印。
 本站是一个以用户分享为主的开源技术平台,欢迎各类分享!
 本文地址:https://www.open-open.com/lib/view/open1441938523555.html
算法