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