转载

继续抄笔记——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

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

正文到此结束