kmp算法是一種字符串按位匹配失效時(shí)的處理辦法。

字符串在匹配時(shí)難免會(huì)出現(xiàn)部分匹配的情況，當(dāng)某一位不匹配時(shí)，順其自然的理解就是子串找錯(cuò)位置了，子串不在這兒（即開(kāi)始的地方就出錯(cuò)了，盡管之前的所有位置都匹配成功）。直接的處理辦法就是母串開(kāi)始位置向后移動(dòng)一位，子串從頭開(kāi)始繼續(xù)找。這就是簡(jiǎn)單粗暴的匹配失效處理辦法。

簡(jiǎn)單粗暴的處理方法中有很強(qiáng)的無(wú)力感，即我承認(rèn)子串不在這，但是前面也確確實(shí)實(shí)匹配到了一部分，沒(méi)必要完全否定從頭開(kāi)始吧。所以kmp出現(xiàn)了，kmp通過(guò)next數(shù)據(jù)記錄了已經(jīng)匹配的部分字符串中可以利用的信息，或者說(shuō)通過(guò)計(jì)算next數(shù)組我們可以沒(méi)必要徹底否定過(guò)去。理解kmp算法的關(guān)鍵也就是理解next數(shù)組。next數(shù)組表示匹配失效時(shí)子串需要重新開(kāi)始匹配的位置（next數(shù)組的意義）。

首先next為子串所有，且與子串長(zhǎng)度相同。next數(shù)組中每一位的值表示子串中該位置之前且不包括該位置的字符串的最長(zhǎng)相同前后綴的長(zhǎng)度（next數(shù)組的計(jì)算方法）。分三步理解：1、next數(shù)組每一位的值表示一個(gè)長(zhǎng)度；2、它是最長(zhǎng)相同前后綴的長(zhǎng)度；3、它是子串中該位置之前且不包括該位置的字符串的最長(zhǎng)相同前后綴的長(zhǎng)度。

其實(shí)到這就說(shuō)清楚了next是什么，非要多說(shuō)一點(diǎn)的話，我認(rèn)為需要理解什么是最長(zhǎng)前后綴。字符串的前綴表示該字符串的一個(gè)切片，該切片以字符串的首字母開(kāi)頭，任意非尾字母結(jié)尾。例：'ABCD'的前綴為‘A’,'AB','ABC'.同理后后綴也是字符串的一個(gè)切片，該切片以任意非首字母開(kāi)頭，以字符串的尾字母結(jié)尾。例：‘ABCD’的后綴為‘D’,'CD',BCD'。

前面說(shuō)next數(shù)組記錄了已經(jīng)匹配的字符串中可以利用的信息。next表示最長(zhǎng)相同前后綴，言外之意就是首尾相同的最大長(zhǎng)度。因?yàn)橹挥挟?dāng)匹配失效時(shí)才會(huì)啟用next數(shù)組，所以可以認(rèn)為失效之前的子串在母串中已經(jīng)全部找到（二者是相同的）即next數(shù)組記錄了子串首部與母串尾部（理解為已經(jīng)匹配的尾部）相同的長(zhǎng)度，根據(jù)next我們完成了把子串的頭與母串的尾（同樣是已經(jīng)匹配的尾部）對(duì)齊的操作。成功利用了已匹配的信息。

講完了，kmp就是這樣一個(gè)根據(jù)已經(jīng)匹配的子串最長(zhǎng)前后綴的長(zhǎng)度決定當(dāng)前匹配失效時(shí)重新開(kāi)始匹配的位置的方法。