理解KMP匹配算法

两篇比较好的文章:阮一峰的网络日志  和 jBoxer

下面是我阅读 Jake Boxer  的文章时做的笔记。应该可以帮助理解。

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个字符长度的模式串,部分匹配表长度也为8.

概念:
前缀:“Snape”的前缀是“S”、“Sn”、“Sna”、“Snap”。
后缀:“Snape”的后缀是“nape”、“ape”、“pe”、“e”。
所以,部分匹配表的含义是:模式串中最长的前缀的长度,这个前缀与模式串中的某个后缀匹配。

具体看看怎样计算部分匹配表里的值:
求index=2位置的value,此时不管index=2之后的字符串,那么字符串是“aba”,前缀为a,ab,后缀为ba,a,这里前缀中与后缀匹配的最长字符串为“a”,长度为1,故位置3的部分匹配表的值为1。
求index=2位置的value,字符串为“abab”,前缀aba,ab,a,后缀bab,ab,b,所有前缀中与后缀匹配的字符串中,最长的长度为2.
以此类推,求得对应index的value值。
求index=4位置的value,字符串为“ababa”,前缀abab,aba,ab,a,后缀baba,aba,ba,a,则前缀中与后缀匹配的最长的字符串是aba,长度为3。

怎样使用部分匹配表
可以使用部分匹配表中的值向前跳过一些重复的比较。
如果有n个字符部分匹配,则可以跳过 n-table[n-1] 个字符。
例如在“bacbababaabcbab”中查找“abababca”。
第一次:

bacbababaabcbab
 |
 abababca

匹配字符个数为n=1, 可跳过的字符数 = n – table[n-1] = 0;
第二次找到有匹配的:

bacbababaabcbab
    |||||
    abababca

此时 n = 5,可跳过的字符数 = n – table[n-1] = 5-table[4] = 2,所以

bacbababaabcbab
    xx|||
      abababca
// x denotes a skip

此时,部分匹配长度为3,可跳过字符数 = n – table[n-1] = 3-table[2] = 2,所以

bacbababaabcbab
      xx|
        abababca
// x denotes a skip

此时模式串已经超出查找字符串,所以,没有找到。

 

 

分享到: 更多
版权申明:

本站保留所有原创文章的版权,本站地址:奔跑的博客[http://www.elecbench.com]

原创文章转载时请注明出处,并添加文章所在页面的链接:http://www.elecbench.com/%e7%90%86%e8%a7%a3kmp%e5%8c%b9%e9%85%8d%e7%ae%97%e6%b3%95/

本站所有 2010年3月4日 以后发表、未标明为“转载”的文章均是本站原创。

发表评论


(设置自己的个性头像)

*

申请属于你的免费顶级域名