kMP算法延伸閱讀

寫在前面的話

這個(gè)博客已經(jīng)荒廢了好久，索性刪掉了之前的題解,，從0開始

這篇文章的目的是為了輔助理解KMP算法,。我的能力也不是很強(qiáng)，這篇文章的定位也只是我自己學(xué)習(xí)過程中的心得總結(jié),。望大家不要生搬硬套,，以理解算法原理為首要目的，最好總結(jié)出自己的寫法,，并在OJ上驗(yàn)證,。在實(shí)踐和比較中加深自己的理解。

正文

kmp算法是一種字符串模式匹配算法,，通過對(duì)于BF(Brute Force)算法的分析可以看出匹配過程中有著這種情況：

例如模式串為abcdabce,，主串為abcdabcdabce

如果按照BF算法，在主串第八個(gè)字符失配,，這時(shí)主串的檢測(cè)位要進(jìn)一,，模式串檢測(cè)位退回到第一個(gè)字符

然而這種情況下的失配一定要從頭開始么

不難看出既然匹配到了模式串的第八位，即主串含有abcdabc,，此時(shí)失配,，可以直接測(cè)試第4位，因?yàn)橛衋bcdabc所以也就有了abc,。

現(xiàn)在對(duì)于這種可優(yōu)化情形進(jìn)行總結(jié),，那就是想要廢物利用當(dāng)前失配情形中已經(jīng)匹配到的那部分串。而利用的方式用語言描述就是告訴計(jì)算機(jī),，如果匹配到這一位失配了,，那么應(yīng)該跳到哪位而這個(gè)指示被放在一個(gè)數(shù)組中，即next數(shù)組

現(xiàn)在對(duì)next數(shù)組的性質(zhì)進(jìn)行分析,，假如在某一位失配之后可以測(cè)試另外一位,，那么說明什么呢？前面說了KMP是廢物利用失配情況的已經(jīng)匹配的部分,，既然已經(jīng)匹配了,，那就是確定了的，之所以敢不從頭匹配而是跳轉(zhuǎn)測(cè)試另外一個(gè)位置就是因?yàn)檫@個(gè)性質(zhì),，而跳轉(zhuǎn)則與這被確定的部分字符串有關(guān),。再回到abcdabce的例子，之所以我們?cè)诘诎宋皇淞酥揽梢灾苯訙y(cè)試第四原因就是第七位之前的abcdabc已經(jīng)確定,，如果把后面的abc單獨(dú)拿出來,，可以發(fā)現(xiàn)這個(gè)abc是模式串的一個(gè)前綴，雖然匹配到當(dāng)前位不能匹配abcdabce但是有可能可以匹配abcd,。

繼續(xù)對(duì)這個(gè)性質(zhì)進(jìn)行描述,，那就是當(dāng)前已經(jīng)成功匹配的部分字符串,，可以截取一個(gè)字符串，要求是從某位置開始,，一直到已經(jīng)成功匹配的字符串的末尾,，而這部分字符串恰好是模式串的一個(gè)前綴。

操作是和目的相關(guān)聯(lián)的,，目的是為了從已經(jīng)成功匹配的部分中找一部分接著匹配,，那么正在被匹配的（剛剛失配的字符位）必須緊接著截取的字符串，所以要截取到已經(jīng)匹配的字符串的末尾,。為了有可能匹配,，截取的這個(gè)字符串必須是模式串的某個(gè)前綴，不然無論失配的位置字符是什么,，它前面就已經(jīng)失配了,，不可能匹配成功。

現(xiàn)在對(duì)于目的進(jìn)行轉(zhuǎn)化,，我們想要有個(gè)next數(shù)組,，而這個(gè)數(shù)組可以告訴我們，這一位前面的字符串可以截取多長(zhǎng)的模式串前綴,。（實(shí)際上是要截取最長(zhǎng)的,，相關(guān)知識(shí)在算法正確性證明部分）而這個(gè)也是kmp在信息學(xué)競(jìng)賽題目中也可用于解部分字符串前綴相關(guān)題目的原因。

有了next數(shù)組之后,，進(jìn)行kmp算法就不難寫出了,，比較的方式和BF算法相同，關(guān)鍵在于對(duì)失配情況的處理,。

先放一道模板題,，建議大家先自己嘗試（kuangbin巨巨的博客里有hdu1711的題解代碼），具體的題解（包含我自己的kmp代碼以及解析,，與教材有區(qū)別）以及kmp算法的正確性證明將在之后發(fā)布,。

模板題

HDU 1711

建議閱讀材料

kuangbin巨巨的博客

c_cloud的博客

P.S.

之前就已經(jīng)多次強(qiáng)調(diào)了，不同的人對(duì)于同一個(gè)算法實(shí)現(xiàn)方式可能不同,，所以如果遇到和教材不符的情形,，

請(qǐng)自行決斷，因?yàn)閮煞N方式?jīng)]有誰對(duì)誰錯(cuò)之分,；

請(qǐng)自擔(dān)后果，因?yàn)閍cm隊(duì)有個(gè)學(xué)長(zhǎng)因?yàn)閷懙拇a和教材偏差太大（這是很正常的,，acm競(jìng)賽有時(shí)會(huì)對(duì)一些數(shù)據(jù)結(jié)構(gòu)和算法進(jìn)行魔改）被老師掛科了,。