Knuth–Morris–Pratt（KMP）是由三位數(shù)學(xué)家克努斯、莫里斯、普拉特同時發(fā)現(xiàn)，所有人們用三個人的名字來稱呼這種算法，KMP是一種改進的字符串匹配算法，它的核心是利用匹配失敗后的信息，盡量減少模式串與主串的匹配次數(shù)以達(dá)到快速匹配的目的。它的時間復(fù)雜度是 O(m+n)
字符匹配：給你兩個字符串 haystack 和 needle ，請你在 haystack 字符串中找出 needle 字符串的第一個匹配項的下標(biāo)（下標(biāo)從 0 開始）。如果 needle 不是 haystack 的一部分，則返回? -1
在介紹KMP算法之前，我們先看一下另一種暴力算法（BF算法）去解字符匹配應(yīng)該怎么做
?BF算法：時間復(fù)雜度O(m*n)
class Solution: def strStr(self, haystack: str, needle: str) -> int: #hi是haystack的當(dāng)前索引 hi = 0 haystackLength = len(haystack) needleLength = len(needle) for i in range(haystackLength - needleLength+1): #每次匹配等于和完整的needle的字符串逐一匹配 if haystack[i:i+needleLength] == needle: return i return -1
KMP算法：時間復(fù)雜度O(m+n)
KMP構(gòu)造了一個next列表來對應(yīng)改位置索引如果匹配失敗應(yīng)該追溯回到什么位置，這樣我們講減少了匹配次數(shù)
?那么我們?nèi)绾稳?gòu)造維護我們的next（最長相同前后綴）
構(gòu)造方法為：next[i] 對應(yīng)的下標(biāo)，為 P[0...i - 1] 的最長公共前綴后綴的長度，令 next[0] = -1。 具體解釋如下：
例如對于字符串 abcba：
??? 前綴：它的前綴包括：a, ab, abc, abcb，不包括本身；
??? 后綴：它的后綴包括：bcba, cba, ba, a，不包括本身；
??? 最長公共前綴后綴：abcba 的前綴和后綴中只有 a 是公共部分，字符串 a 的長度為 1
我們通過動態(tài)規(guī)劃來維護next，假設(shè)你知道next[0:i-1]位置上所有的回溯值，那么next[i-1]和next[i]相比僅僅多了一個位置，如果這個多的字符可以匹配上，那么next[i]一定等于next[i-1]+1(如下圖所示)
那么如果匹配不上呢，匹配不上我們回溯到next[i-1]所需要回溯的位置，直到可以匹配上或到達(dá)無法追溯的位置next[0] = -1
@staticmethod def same_start_end_str(p): """ 通過needle串來知道每個索引位置對應(yīng)的最長前后綴 例如ababa的最長前后綴是aba，前后綴是不和needle等長的最長相同前后綴 """ next = [-1] * (len(p)+1) si = -1 ei = 0 pl = len(p) while ei < pl : if si == -1 or p[si] == p[ei]: si += 1 ei += 1 next[ei] = si else: #無法匹配上，繼續(xù)向前追溯 si = next[si] return next
那我們有了next就可以取實現(xiàn)我們KMP算法了，完整代碼如下文章來源：http://www.zghlxwxcb.cn/news/detail-741783.html
class Solution: def strStr(self, haystack: str, needle: str) -> int: next = self.same_start_end_str(needle) #hi是haystack當(dāng)前索引,ni是needle當(dāng)前索引 hi = ni = 0 hl = len(haystack) nl = len(needle) while hi < hl and ni < nl: if ni == -1 or haystack[hi] == needle[ni]: hi += 1 ni += 1 else: ni = next[ni] if ni == nl: return hi - ni else: return -1 @staticmethod def same_start_end_str(p): """ 通過needle串來知道每個索引位置對應(yīng)的最長前后綴 例如ababa的最長前后綴是aba，前后綴是不和needle等長的最長相同前后綴 """ next = [-1] * (len(p)+1) si = -1 ei = 0 pl = len(p) while ei < pl : if si == -1 or p[si] == p[ei]: si += 1 ei += 1 next[ei] = si else: #無法匹配上，繼續(xù)向前追溯 si = next[si] return next
?文章來源地址http://www.zghlxwxcb.cn/news/detail-741783.html
到了這里，關(guān)于字符串匹配算法：KMP的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
