About KMP
发现很多地方把 KMP 算法介绍得不完全正确，说
text: a b a b b a b b b . . . pattern: a b a b a c b
这一次匹配尝试失败之后下一步尝试是：
text: a b a b b a b b b . . . pattern: a b a b a c b
不过 KMP，至少根据 “FAST PATTERN MATCHING IN STRINGS” 论文本身的说法以及 这里 的介绍，比较聪明——它会发现右移两位之后出现在不匹配位置的还是同样一个不匹配的字符。
所以，实际上可以右移五位：
text: a b a b b a b b b . . . pattern: a b a b . . .
这才是 KMP。
而上面的，貌似是 MP 算法。
PS，强烈建议看看 Fast Pattern Matching in Strings 这篇论文，写得可好了——18页之后还有个大大的惊喜： Knuth 爷爷在 Postscript 中很详细的介绍并分析了 Boyer-Moore 算法。
Licensed under CC Attribution-NonCommercial-NoDerivs 3.0 Unported License
Author: If
转载请注明：来自 IF's
本文地址： http://www.if-yu.info/2010/08/11/about-kmp.html
Trackback:http://www.if-yu.info/2010/08/11/about-kmp.html?code=aghpYW15dWd1b3INCxIFRW50cnkYqbEHDA
0 comments
add a comment