KMP字符串匹配算法
昨天意外的翻开一本搜索引擎的书，看到了KMP算法，很早以前就听过KMP算法，但是没有深究，最近在搞搜索，所以想深入学习一下KMP算法。KMP算法是一种改进的字符串匹配算法。KMP算法的核心是通过匹配表来提高匹配效率，理解了匹配表就基本理解了KMP算法。核心思想是利用已经得到的部分匹配信息来进行后面的匹配过程。我认为优秀算法的根本是减少不必要的重复计算从而提升效率。
介绍两个概念：
前缀：除字符串的最后一个字符外，所有前缀组合
后缀：除了字符串的第一个字符外，所有后缀组合
例如：Google，前缀：G、Go、Goo、Goog、Googl
后缀：o、oo、oog、oogl、oogle
那么匹配表怎么算呢，找到”前缀和后缀集合中最长匹配的字符串的长度“。
例如：abababca
a的前缀后缀都为空 L=0
ab的前缀为a后缀为b L=0
aba的前缀a、ab后缀a、ba，L=1
abab的前缀a、ab、aba后缀b、ab、bab，L=2
ababa的前缀a、ab、aba、abab后缀baba、aba、ba、a，L=3
ababab的前缀a、ab、aba、abab、ababa后缀babab、abab、bab、ab、b，L=4
abababc的前缀a、ab、aba、abab、ababa、ababab后缀bababc、ababc、babc、abc、bc、c，L=0
abababca的前缀a、ab、aba、abab、ababa、ababab、abababc后缀bababca、ababca、babca、abca、bca、ca、a，L=1
生成匹配表如下
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 |
table[partial_match_length - 1]>利用partial_match_length - table[partial_match_length - 1]计算可以跳过的位移。
例如bacbababaabcbab中匹配abababca
| b | a | c | b | a | b | a | b | a | a | b | c | b | a | b |
| X | ||||||||||||||
| a | b | a | b | a | b | c | a |
没有匹配，下移一位：
| b | a | c | b | a | b | a | b | a | a | b | c | b | a | b |
| | | ||||||||||||||
| a | b | a | b | a | b | c | a |
table[partial_match_length - 1]= table[0]) = 0，1-0=1.下移一位
| b | a | c | b | a | b | a | b | a | a | b | c | b | a | b |
| X | ||||||||||||||
| a | b | a | b | a | b | c | a | |
未匹配，下移一位，一次类推，直到匹配
| b | a | c | b | a | b | a | b | a | a | b | c | b | a | b |
| | | | | | | | | | | ||||||||||
| a | b | a | b | a | b | c | a | |
匹配了5项，partial_match_length-5，partial_match_length - table[partial_match_length - 1]=5-table[4]=5-3=2
| b | a | c | b | a | b | a | b | a | a | b | c | b | a | b |
| a | b | a | a | b | c | a | |
位移两位的实质是：在已匹配的字符串ababa中，前缀为a、ab、aba、abab，后缀为baba、aba、ba、a，其中前缀和后缀集合中相同项为a、aba，aba最长。正如下面的变换所示，partial_match_length -3=5-3=2.需要移动两位。总匹配长度为5，有3个字符串前缀和后缀是匹配的，所有需要用总匹配长度减去前后缀匹配长度，即为位移数。
| a | b | a | b | a |
| | | | | | | ||
| a | b | a | ||
| | | | | | | ||
| a | b | a |
参考：The Knuth-Morris-Pratt Algorithm in my own words
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
