字符串的匹配在平常的編碼過(guò)程中非常常用湿酸，在編程語(yǔ)言中通常是調(diào)用一個(gè)內(nèi)置函數(shù)就可以實(shí)現(xiàn)字符串的匹配辜御，當(dāng)不讓使用內(nèi)置的函數(shù)伍派，而是自己編寫(xiě)一個(gè)函數(shù)來(lái)實(shí)現(xiàn)匹配的功能江耀，應(yīng)該如何來(lái)寫(xiě)呢？
今天介紹兩個(gè)算法诉植，樸素匹配算法祥国，和無(wú)回溯匹配算法中的KMP算法。
樸素匹配算法
樸素匹配算法就是按照常識(shí)來(lái)晾腔，最容易理解的逐個(gè)字符匹配舌稀。
從待匹配字符串中的某個(gè)下標(biāo)i開(kāi)始，匹配字符串從0開(kāi)始灼擂，逐個(gè)匹配壁查。當(dāng)有不匹配的字符時(shí)，重新從i+1下標(biāo)開(kāi)始重復(fù)上次的匹配過(guò)程剔应。
下面用代碼實(shí)現(xiàn)一下：
t表示待匹配字符串睡腿，p表示用來(lái)匹配的字符串。
表示p字符串的第i個(gè)下標(biāo)的字符峻贮。
def naive_match(t, p):
"""
t 目標(biāo)字符串
p 匹配字符串
"""
m, n = len(p), len(t)
i, j = 0, 0
while i < m and j < n:
if p[i] == t[j]: # 字符相同席怪，考慮下一字符
i, j = i + 1, j + 1
else:
i, j = 0, j - i + 1 # 字符不同，查找字符串重置月洛，目標(biāo)字符串回溯
if i == m:
return j - i
return -1
樸素匹配算法非常簡(jiǎn)單何恶，容易理解。當(dāng)然嚼黔，它的效率也是很低的细层，造成效率低的原因是在執(zhí)行過(guò)程中會(huì)有回溯惜辑。當(dāng)遇到p[i] != t[j]時(shí)，匹配字符串下標(biāo)置0疫赎，待匹配字符串的下標(biāo)回到上一次檢查的下一個(gè)位置盛撑，往回退了j - i + 1個(gè)位置。
這種操作造成的效率很低捧搞。最壞的情況是抵卫，每次匹配都是到最后一個(gè)字符的時(shí)候不匹配。例如：
??待匹配字符串： 0000000000001
??匹配字符串： 00001
這樣需要 n-m+1次比較胎撇，總的比較次數(shù)就是(n-m+1) * m介粘，這樣它的復(fù)雜度就是：O(n*m)
KMP算法
樸素算法的效率低，根源上是把每次匹配都看成的單獨(dú)的事件晚树，沒(méi)有利用到之前的匹配信息姻采。而其他改進(jìn)算法就是利用了之前的匹配信息。
KMP算法的基本思想就是在匹配中不回溯爵憎。
描述KMP算法慨亲，需要借助上圖。
待匹配字符串t宝鼓，和匹配字符串p刑棵。
在匹配過(guò)程中，p的第i個(gè)字符在和t的第j個(gè)字符比較愚铡，這時(shí)蛉签，～
和
～
相等，匹配完成茂附。下面要做的步驟可以分為兩個(gè)：
- 當(dāng)
時(shí)正蛙，繼續(xù)進(jìn)行下一個(gè)字符的比較。
- 當(dāng)
時(shí)营曼，這是不需要重置
p，而是找到一個(gè)位置k()愚隧，使得
～
等于
～
蒂阱，繼續(xù)匹配
和
，重復(fù)上面的步驟狂塘。這樣待匹配字符串也不需要回溯到前面去重新匹配录煤。
KMP算法中的關(guān)鍵認(rèn)識(shí)是：在匹配失敗時(shí)，所有的
(
)都已經(jīng)匹配成功荞胡。也就是說(shuō)妈踊，待匹配字符串中的
之前的i個(gè)字符，與匹配字符串中的前i個(gè)字符
泪漂。
通過(guò)上面的分析廊营，要找到k歪泳，完全可以先不管待匹配字符串，而是研究一下匹配字符串p露筒，通過(guò)p找到它前移的位置k呐伞。
得出一個(gè)結(jié)論：在p中，其中的每一個(gè)字符的i都會(huì)有其對(duì)應(yīng)的下標(biāo)k慎式，與待匹配的字符串無(wú)關(guān)伶氢。
因此，我們可以為匹配字符串設(shè)計(jì)一個(gè)列表來(lái)存儲(chǔ)每一個(gè)i的下標(biāo)k瘪吏。假設(shè)p的長(zhǎng)度為m癣防，用一個(gè)長(zhǎng)度為m的列表pnext來(lái)存儲(chǔ)，用表元素pnext[i]來(lái)表示i個(gè)元素的下標(biāo)k值掌眠。
有一種特殊情況：匹配失敗后蕾盯，之前所做的匹配都沒(méi)有用，需要從頭開(kāi)始匹配扇救，用
與
比較刑枝。在這種特殊情況下可以在
pnext[i]中存入-1來(lái)表示。顯然迅腔，一直為-1装畅。
KMP主算法
當(dāng)假設(shè)pnext已經(jīng)獲得了，KMP的算法實(shí)現(xiàn)為：
def kmp_match(t, p, pnext):
"""
KMP匹配沧烈，主函數(shù)
"""
i, j = 0, 0
m, n = len(p), len(t)
while i < m and j < n:
if i == -1: # -1 匹配下一隊(duì)字符
i, j = i + 1, j + 1
elif p[i] == t[j]: # 相等掠兄，匹配下一對(duì)字符
i, j = i + 1, j + 1
else:
i = pnext[i] # 從pnext中拿出下一個(gè)字符應(yīng)該的位置
if i == m:
return j - i
return -1
該算法的時(shí)間復(fù)雜度為O(n)，因?yàn)閖的循環(huán)次數(shù)不會(huì)超過(guò)n锌雀，i = pnext[i]的次數(shù)不會(huì)超過(guò)m蚂夕。
pnext的實(shí)現(xiàn)
最長(zhǎng)相等前后綴
已知pnext[0]=-1，并且pnext[0]到pnext[i-1]已知的情況下腋逆，求解pnext[i]:
- 假設(shè)
pnext[i-1]=k-1婿牍，如果，則
的最長(zhǎng)的匹配相等長(zhǎng)度為k惩歉，記下
pnext[i]=k等脂。 - 如果
，就將k的值設(shè)為pnext[k]撑蚌，即考慮前一個(gè)保證匹配的字符串上遥，且更短。
- 假如k的值為-1（由第二步造成争涌，一直到不到可以匹配的字符串）粉楚，那么就將pnext[i]設(shè)置為0，將i遞增后繼續(xù)檢查。
構(gòu)造方法如下：
def gen_pnext(p):
i, k, m = 0, -1, len(p)
pnext = [-1] * m
while i < m - 1:
if k == -1 or p[i] == p[k]:
i, k = i + 1, k + 1
pnext[i] = k
else:
k = pnext[k]
return pnext
舉例：匹配字符串為 abbcabcaabbcaa模软，得到的pnext為：
[-1, 0, 0, 0, 0, 1, 2, 0, 1, 1, 2, 3, 4, 5]
pnext生成算法的改進(jìn)
在pnext的生成中伟骨，對(duì)pnext[i]的設(shè)置可以有些優(yōu)化。
在圖(2)中撵摆，匹配失敗底靠，假設(shè)pnext[i]=k，如果發(fā)現(xiàn)
特铝，那么也一定有
暑中，所以，這種情況下pnext[i]的位置移動(dòng)到pnext[k]鲫剿，這一修改減少了一個(gè)比較步驟鳄逾，有可能提高效率。修改后：
def gen_pnext(p):
i, k, m = 0, -1, len(p)
pnext = [-1] * m
while i < m - 1:
if k == -1 or p[i] == p[k]:
i, k = i + 1, k + 1
if p[i] == p[k]:
pnext[i] = pnext[k]
else:
pnext[i] = k
else:
k = pnext[k]
return pnext
舉例：匹配字符串為 abbcabcaabbcaa灵莲，得到的pnext為：
[-1, 0, 0, 0, -1, 0, 2, -1, 1, 0, 0, 0, -1, 5]
pnext的復(fù)雜度為O(m)雕凹，所以整個(gè)KMP算法的復(fù)雜度O(m+n)，由于m小于n政冻，可以認(rèn)為復(fù)雜度為O(n)枚抵，優(yōu)于樸素算法。
轉(zhuǎn)載自：
https://codeeper.com/2020/05/23/tech/python/structure/str-search-and-kmp.html
