KMP算法

chg668 8年前

来自: http://www.loyhome.com/继续抄笔记-kmp算法/

在今天以前我也不知道有个大名鼎鼎的KMP算法,也是偶然看到的。KMP算法解决的是文本匹配的问题,比如我要在字符串“今天天气特别好”里面找到“特别”的位置(对应第5-6位),或者简单如我在word里面点击“查找”,然后搜索一个关键词。一般来说,如果是编程中为了解决这种问题,我就特别习惯的去写正则表达式了...从没想过正则表达式后面他们到底会怎么算。当然直到此刻我也不知道正则表达式会不会调用KMP算法。

在上面那个例子中,只要我慢慢从左到右一个个对比“今天天气特别好”和“特别”就很容易找到“特别”的位置,无非就是到第5位的时候发现“特”是匹配上的,然后对比一下第6位是不是一样。但是如果前面那句话变成了“今天特热,但天气特别好”,按照上面的算法,我就会在第三位发现“特”是匹配上的,但是第四位没有匹配到,于是我又开始从第四位开始重新一个个看、什么时候可以依次匹配到“特”和“别”。

这大概是最直观的算法了,写起来也并不麻烦。就是有点暴力的感觉:穷尽所有的可能、总能找得到是不是。

当查找的字符串简单如“特别”的时候,确实用不用kmp算法不会有任何区别。可是有的时候我们要查找的字符串比较长,那这样的暴力算法就有点浪费了——因为可能已经做过一些比较了。

举个例子。我现在想在“今天天气很好,街上人来人往好不热闹,我们一起出去玩好不好”这句话中寻找“好不好”。那么第一个“好”出现在“今天天气很 好 ”,然后发现嗯,下面一个是逗号,所以继续从逗号开始找下一个“好”;然后找到“ 好不 热闹”,发现“好不”都被匹配到了,但是最后一个“好”没有匹配到,所以我们还得继续找。那么这时候是应该直接跳到哪里呢?“闹”、“热闹”呢,还是“不热闹”这里开始比较?显然看我们要寻找的字符串,“好不好”的第一位和第三位是一样的,然后第二位和他们俩都不一样,所以我们其实知道在“好不热闹”这个局部中,第二位的“不”不可能和“好”匹配,第三位的“热”也不可能和“好”匹配,所以我们可以直接跳到第四位“闹”。

这大概就是kmp的基本直觉了:先看一下我要搜寻的这个东西自己是不是有一定的模式,算一张局部匹配表(Partial Match Table),然后按照这个表就可以知道当每次前面部分匹配、而后面不匹配的时候,可以直接跳过几个格子往下走。(至于这个表格怎么算的,还是有点麻烦的....)

我是看这个解释看懂的:

http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/

然后matrix67也有一篇有点历史的文章来解释这个: http://www.matrix67.com/blog/archives/115