Kmp

字符串匹配算法总结 KMP虽然经典,但是理解起来极其复杂,好不容易理解好了,便起码来巨麻烦！ 老子就是今天图书馆在写了几个小时才勉强写了一个有bug的、效率不高的KMP,特别是计算next数组的部分。 其实,比KMP算法速度快的算法大把大把,而且理解起来更简单,为何非要抓住KMP呢？笔试出现字符串模式匹配时直接上sunday算法,既简单又高效,何乐而不为？ 说实话,想到sunday算法的那个人,绝对是发散思维,绝对牛。当我在被KMP折磨的够呛的时候,我就琢磨,有没有别的好算法呢？？琢磨了半天也没想出个所以然来。笨啊,脑子不够发散。 下面贴上一位兄弟写的算法总结,很简单 (建议KMP部分就不用看了,看了费脑子) 。 参见: http://hi.baidu.com/willamette/blog/item/02bd0b5599c8b4c0b645ae06.html 趁着做Presentation的功夫,顺便做一个总结 字符串匹配: -willamette 在匹配串中寻找模式串是否出现,注意和最长公共子序列相区别(LCS: Longest Common Substring) **-: ** Brute Force(BF或蛮力搜索) **算法: ** 这是世界上最简单的算法了。 首先将匹配串和模式串左对齐,然后从左向右一个一个进行比较,如果不成功则模式串向右移动一个单位。 速度最慢。 那么,怎么改进呢？ 我们注意到Brute Force 算法是每次移动一个单位,一个一个单位移动显然太慢,是不是可以找到一些办法,让每次能够让模式串多移动一些位置呢？ 当然是可以的。 我们也注意到,Brute Force 是很不intelligent 的,每次匹配不成功的时候,前面匹配成功的信息都被当作废物丢弃了,当然,就如现在的变废为宝一样,我们也同样可以将前面匹配成功的信息利用起来,极大地减少计算机的处理时间,节省成本。^_^ 注意,蛮力搜索算法虽然速度慢,但其很通用,文章最后会有一些更多的关于蛮力搜索的信息。 **-: KMP算法 ** 首先介绍的就是KMP 算法。 原始论文: Knuth D.E., Morris J.H., and Pratt V.R., Fast pattern matching in strings, SIAM Journal on Computing, 6(2), 323-350, 1977. 这个算法实在是太有名了,大学上的算法课程除了最笨的Brute Force 算法,然后就介绍了KMP 算法。也难怪,呵呵。谁让Knuth D.E. 这么world famous 呢,不仅拿了图灵奖,而且还写出了计算机界的Bible 《The Art of Computer Programming》( 业内人士一般简称TAOCP). 稍稍提一下,有个叫H.A.Simon 的家伙,不仅拿了Turing Award ,顺手拿了个Nobel Economics Award ,做了AI 的爸爸,还是Chicago Univ 的Politics PhD ,可谓全才。 ...