每一本《數(shù)據(jù)結(jié)構(gòu)》方面的書(shū)應(yīng)該都會(huì)講KMP算法，KMP算法可以說(shuō)是知名度非常高的算法之一，為什么會(huì)叫做KMP算法？是因?yàn)?/span>KMP是由三位大牛：D.E.Knuth、J.H.Morris和V.R.Pratt幾乎同時(shí)發(fā)現(xiàn)的。所以取了每個(gè)人的第一個(gè)字母叫做KMP算法。

給你一個(gè)母串和一個(gè)子串；請(qǐng)?jiān)谀复袑ふ易哟绻复写嬖谧哟畡t返回True，不存在則返回False。

示例：母串：ababababcabc，子串：abababca

輸入：ababababcabc

   abababca

輸出：True

如KMP算法的時(shí)間復(fù)雜度為O（m+n）比暴力破解的時(shí)間復(fù)雜度O（m*n）小很多，這是因?yàn)樵?/span>KMP算法中子串和母串不匹配的時(shí)候不會(huì)將子串向右挪移1位，而是將子串向后挪移k位。

如何確定子串向后挪移的位數(shù)呢？這個(gè)就像需要建立next數(shù)組來(lái)進(jìn)行匹配，next數(shù)組就是子串中每一個(gè)位置的最大公共長(zhǎng)度。最大公共長(zhǎng)度在算法導(dǎo)論里面就被記為next數(shù)組。

計(jì)算next數(shù)組就是計(jì)算子串中每一個(gè)位置的最大公共長(zhǎng)度。簡(jiǎn)單來(lái)說(shuō)可以理解為遮住這個(gè)元素，去查看這個(gè)元素前面的相同前綴和后綴的長(zhǎng)度，這個(gè)長(zhǎng)度就是該元素對(duì)應(yīng)的值，如圖。

確定next數(shù)組后我們就可以開(kāi)始子串與母串的匹配，當(dāng)匹配到的元素值不同時(shí)，查找子串中該元素對(duì)應(yīng)的next值，根據(jù)next值來(lái)確定子串該如何移動(dòng)，移動(dòng)后再開(kāi)始新一次的匹配，一直循環(huán)這個(gè)過(guò)程直到匹配結(jié)束。

KMP算法的核心就是在于next數(shù)組的建立，建立正確的next數(shù)組至關(guān)重要，通過(guò)next數(shù)組里面的next值可以幫助我們有效的減少循環(huán)次數(shù)和節(jié)約大量的時(shí)間。

實(shí)習(xí)編輯：李欣容

作者：陳東