以前看過(guò)kmp算法，當(dāng)時(shí)接觸后總感覺(jué)好深?yuàn)W啊，抱著數(shù)據(jù)結(jié)構(gòu)的數(shù)啃了一中午，最終才大致看懂，后來(lái)提起kmp也只剩下“奧，它是做模式匹配的”這點(diǎn)干貨。最近有空，翻出來(lái)算法導(dǎo)論看看，原來(lái)就是這么簡(jiǎn)單（下不說(shuō)程序?qū)崿F(xiàn)，思想很簡(jiǎn)單）。

模式匹配的經(jīng)典應(yīng)用：從一個(gè)字符串中找到模式字串的位置。如“abcdef”中“cde”出現(xiàn)在原串第三個(gè)位置。從基礎(chǔ)看起

樸素的模式匹配算法

A：abcdefg  B：cde

首先B從A的第一位開(kāi)始比較，B++==A++，如果全部成立，返回即可；如果不成立，跳出，從A的第二位開(kāi)始比較，以此類推。

思路樸實(shí)無(wú)華，十分有效，但是時(shí)間復(fù)雜度是O(mn)，m、n分別是字符串和模式串的長(zhǎng)度。模式匹配是一個(gè)常見(jiàn)的應(yīng)用問(wèn)題，用的廣了，就有人想法去優(yōu)化了。Rabin-Karp算法、有限自動(dòng)機(jī)等等，前仆后繼，最終出現(xiàn)了KMP(Knuth-Morris-Pratt)算法。

kmp算法

優(yōu)化的地方：如果我們知道模式中a和后面的是不相等的，那么第一次比較后，發(fā)現(xiàn)后面的的4個(gè)字符均對(duì)應(yīng)相等，可見(jiàn)a下次匹配的位置可以直接定位到f了。說(shuō)明主串對(duì)應(yīng)位置i的回溯是不必要的。這是kmp最基本最關(guān)鍵的思想和目標(biāo)。

再比如：

由于abc 與后面的abc相等，可以直接得到紅色的部分。而且根據(jù)前一次比較的結(jié)果，abc就不需要比較了，現(xiàn)在只需從f-a處開(kāi)始比較即可。說(shuō)明主串對(duì)應(yīng)位置i的回溯是不必要的。要變化的是模式串中j的位置（j不一定是從1開(kāi)始的，比如第二個(gè)例子）

j的變化取決于模式串的前后綴的相似度，例2中abc和abc（靠近x的），前綴為abc，j=4開(kāi)始執(zhí)行。

j是前一次執(zhí)行的模式子串（前幾個(gè)，上例為6）中前綴的個(gè)數(shù)+1；它與模式字串中從前向后的前綴和從后向前的后綴的相同子串是有關(guān)系的，因?yàn)橄麓芜@部分相同的前綴就會(huì)移動(dòng)到這部分后綴的位置，因?yàn)槿绻苿?dòng)到后綴的前面位置，看圖：

所以如果這次是j，下次的位置應(yīng)該就是j前面的子串的最大前綴的長(zhǎng)度+1,用這個(gè)新的位置再和原字符串的i位置進(jìn)行比較就很幸福了。

這次是j，下次到底是多少呢，這就涉及到怎么計(jì)算的問(wèn)題了？其實(shí)只看模式串我們就可以構(gòu)建出這個(gè)j->x的關(guān)系，關(guān)系稱為前綴函數(shù)，結(jié)果存儲(chǔ)在數(shù)組中，稱為前綴數(shù)組。

偽代碼：

使用前綴數(shù)組可很快地實(shí)現(xiàn)模式匹配，程序匹配字符串中模式出現(xiàn)的所有位置。

這兩段代碼思想完全相同,如果和前綴不同就比較前綴的前綴…，比較巧妙。如果kmp有難理解的地方，估計(jì)就是這段偽碼的了。

KMP算法的時(shí)間復(fù)雜度為O(n+m)。

這里需要強(qiáng)調(diào)一下，KMP算法的僅當(dāng)模式與主串之間存在很多部分匹配情況下才能體現(xiàn)它的優(yōu)勢(shì)，部分匹配時(shí)KMP的i不需要回溯，否則和樸素模式匹配沒(méi)有什么差別。