對于長度為 n 的字符串 S,以及一個長度為 m (m<=n) 的字符串 s,尋找 s 在 S 中第一次出現(xiàn)的位置.

樸素的解法時間復(fù)雜度是 O(m×n)

KMP算法的時間復(fù)雜度是 O(m+n)

相比于樸素解法匹配失敗就指針回退,KMP算法則是標(biāo)記 S 的指針不回退,標(biāo)記 s 的指針根據(jù)一個函數(shù)(回退函數(shù),前綴函數(shù),部分匹配表,失配函數(shù)等都是這個東西的翻譯,似乎每個網(wǎng)站的翻譯甚至同一個網(wǎng)站不同的作者翻譯都是不一樣的...)部分回退,從而節(jié)省了大量時間.

這個回退函數(shù)的基本原理就是通過預(yù)處理字符串 s ,找到 s 中前綴相同的部分,計算每個位置匹配失敗的時候需要回退的值,以便于在匹配失敗的時候不用整個后退.

所以關(guān)鍵問題就轉(zhuǎn)化成了如何求解回退函數(shù),基本思想就是尋找 s 中各個子串的最長公共前綴.

就寫這么多吧,希望以后的自己能看懂.