字符串匹配:KMP算法, Boyer-Moore算法理解与总结

1. KMP算法是前缀匹配算法,一次从前往后匹配的过程中,根据已经部分匹配的信息,在文本中,移动尽可能远的距离。而不是按照朴素模式匹配方法,每次都只移动一个位置。

比如这个示例,在文本串中从4(从0开始编号)开始逐个字符匹配,直到某个不匹配的字符(空格和D),然后朴素模式匹配算法是从下一个字符继续开始。而KMP算法,就是根据已经匹配的部分信息"ABCDAB"和模式串,直接从第二个AB开始下一轮的匹配!

"部分匹配"的实质是,有时候,字符串头部和尾部会有重复。比如,"ABCDAB"之中有两个"AB",那么它的"部分匹配值"就是2("AB"的长度)。搜索词移动的时候,第一个"AB"向后移动4位(字符串长度-部分匹配值),就可以来到第二个"AB"的位置。

 

2. BM算法是后缀匹配算法,从后往前开始匹配。而每次当遇到不匹配的字符时,则根据已经匹配的后缀信息,从尽可能远的位置开始匹配!

此时I是坏字符,且I不在模式串"EXAMPLE"中,假如根据坏字符规则:那么模式串开始跟I的下一个字符M对齐,然后开始下一轮匹配。

但是这里没有充分利用已经匹配的后缀,由于后缀"MPLE" 已经匹配,模式串的第一个字符时E,肯定跟坏字符I的下一个字符M不等,所以这里应该利用好后缀,把模式串移动尽可能远的距离,开始下一轮的匹配。

这里模式串的第一个字符为E,所以直接从好后缀中,第一次出现E的位置开始下一轮的匹配!

注意这里:为什么要从好后缀中第一个出现模式串开始字符E的地方开始匹配呢?因为BM算法是后缀匹配算法,从后往前匹配,所以在一轮匹配匹配过程中,已经扫描过了模式串和文本串直到第一次坏字符的位置,但是模式串之前的字符是什么不知道,所以从好后缀中第一个出现模式串开始字符E的地方开始匹配。

所以,在每一轮匹配过程中,不匹配时,BM算法就是根据坏字符规则和好后缀,把模式串移动尽可能远的距离,开始下一轮的匹配!

 

 总结:KMP算法和BM算法的思想,都是充分部分匹配和文本串当前字符、模式串字符不匹配时所隐含的信息,把模式串移动尽可能远的距离,开始下一轮的匹配!

参考资料:

http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html

http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

http://www.cnblogs.com/gaochundong/p/boyer_moore_string_matching_algorithm.html

http://www.cnblogs.com/gaochundong/p/string_matching.html

 

原文地址:https://www.cnblogs.com/bitpeng/p/4750151.html