Python實現(xiàn)KPM算法詳解
知識點說明：
先說前綴，和后綴吧
比如有一個串：abab
則在下標為3處的（前綴和后綴都要比下標出的長度小1，此處下標為3出的長度是4）
前綴為：a,ab,aba
后綴為：b,ba,bab
一、要獲取KPM算法的next[]數(shù)組
簡單說一下原理吧，首先k，用來存放前綴的下標，首先初始化j=0（j用來表示模式串的下標，一直去模式串的每一位與前面的進行比較，如果相等，則記錄下當前位置與前面的哪個位置相同，我們這里主要是要記錄相同位置的下一個位置，就是不相同的位置，從不相同的位置開始比較，就是回溯到不相同位置，所以這里在t[j]==t[k]成立的時候要j+1，為了比較下一個位置是否相同，k也要+1），模式串從0開始，k=-1，next[0]=-1第一個位置賦默認值-1；
此處串采用=“abab”
第一次循環(huán)：
判斷k是否等于-1，如果等于則，j和k都+1，
此時j=1，k=0，next[1]=0，也就是第2個位置（下標1）的回溯位置還是0，因為前綴的最大長度必須小于當前位置的長度；
第二次循環(huán)：
j=1，k=0，next[1]=0；k已經(jīng)不等于-1了，判斷t[j]==t[k]，t[1]==t[0]，t[1]="b"，t[0]="a"，不相等
執(zhí)行else：
k=next[0]=-1
第三次循環(huán)：
k==-1
j和k都+1，j=2，k=0,next[2]=0
第四次循環(huán)：
k不等于-1，判斷t[2]==t[0]，t[2]=“a”=t[0]=“a”，成立
j和k都+1，j=3，k=1，next[3]=1
此時next=[-1,0,0,1]，next[3]=1表示在next[3]處發(fā)生不匹配時，也就是模式串下標為3時為“b”，說明前面aba都是和目標串都匹配，所以模式串不匹配位置前面的串aba一定與目標串不匹配位置前面的前3個值相等，也就是aba，所以此刻，只需要回溯到模式串的1位置，也就是模式串的b，模式串b前面是a，滿足目標串的前一個a。
第五次循環(huán)：
k依舊是不等于-1，就是比較上一個位置后面的兩個數(shù)再進行比較，簡單的說，以此取出每一項與第一項比較，如果存在相等的就再比較下一個與第二項是否相等。
代碼如下：
def GetNext(t, next):
j, k = 0, -1
next[0] = -1
while j < len(t) - 1:
if k == -1 or t[j] == t[k]: # 如果k==-1 或者 開始位置和結尾位置有相同的元素
j, k = j + 1, k + 1 # j和k都加1,當前位匹配，則從下一個位置開始匹配，所以k+1；j再進行取下一位判斷是否也是匹配，所以也要+1
next[j] = k # 當前位置要取k項
else:#如果不相等，再把k置-1，下一次循環(huán)再進行+1操作，j這個位置再存入0，表示無匹配項
k = next[k]
return next
二、KMP函數(shù)
原理和BF算法是一樣的，唯獨不同的是，當模式串與目標串不匹配的時候，不直接回溯模式串，而是根據(jù)模式串的next[]表，查詢要回溯到的位置，直接回溯到模式串的指定位置，KMP算法的核心也就在這里，但是這種方法一般只對前綴和后綴存在相同元素時，有效果，也就是說相同部分是一樣的就不再進行比較了，從相同元素的下一個位置開始比較，所以KMP算法最復雜的部分其實就是找next[]表，要找出模式串的每一個位置，是否有相同前綴，如果有則標注該相同位置，下次回溯就不用回溯到0這個位置，可以從不相同位置開始。
def KMP(s, t):
next = [0] * len(t)
next = GetNext(t, next)
print(next)
i, j = 0, 0
while i < len(s) and j < len(t):
if j == -1 or s[i] == t[j]:
i, j = i + 1, j + 1
else:
j = next[j]
if j >= len(t):
return i - len(t)
else:
return -1
完整代碼：
def GetNext(t, next):
j, k = 0, -1
next[0] = -1
while j < len(t) - 1:
if k == -1 or t[j] == t[k]: # 如果k==-1 或者 開始位置和結尾位置有相同的元素
j, k = j + 1, k + 1 # j和k都加1,當前位匹配，則從下一個位置開始匹配，所以k+1；j再進行取下一位判斷是否也是匹配，所以也要+1
next[j] = k # 當前位置要取k項
else:#如果不相等，再把k置-1，下一次循環(huán)再進行+1操作，j這個位置再存入0，表示無匹配項
k = next[k]
return next
def KMP(s, t):
next = [0] * len(t)
next = GetNext(t, next)
print(next)
i, j = 0, 0
while i < len(s) and j < len(t):
if j == -1 or s[i] == t[j]:
i, j = i + 1, j + 1
else:
j = next[j]
if j >= len(t):
return i - len(t)
else:
return -1
if __name__ == '__main__':
re = KMP('asdfghjsssaaasdfaaaabababcdabd', "ababaaaababaa")
print(re)
結果：
到此這篇關于Python實現(xiàn)KPM算法詳解的文章就介紹到這了,更多相關Python KPM算法內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
使用Python進行網(wǎng)絡數(shù)據(jù)可視化的多種方法與技巧
可視化是理解和解釋大量數(shù)據(jù)的強大工具之一,而Python作為一種流行的編程語言,提供了豐富的庫和工具來進行網(wǎng)絡數(shù)據(jù)可視化,本文將介紹一些使用Python進行網(wǎng)絡數(shù)據(jù)可視化的方法與技巧,并提供相應的代碼實例,需要的朋友可以參考下2024-05-05
這篇文章主要介紹了Python生成密碼庫功能,涉及Python基于隨機字符串實現(xiàn)的生成密碼功能相關操作技巧,需要的朋友可以參考下2017-05-05
這篇文章主要介紹了Django 遷移、操作數(shù)據(jù)庫的相關知識，本文給大家介紹的非常詳細，具有一定的參考借鑒價值,需要的朋友可以參考下2019-08-08
在計算機程序設計中，回調函數(shù)，或簡稱回調（Callback），是指通過函數(shù)參數(shù)傳遞到其它代碼的，某一塊可執(zhí)行代碼的引用。這一設計允許了底層代碼調用在高層定義的子程序2014-01-01
Python通過Schema實現(xiàn)數(shù)據(jù)驗證方式
這篇文章主要介紹了Python通過Schema實現(xiàn)數(shù)據(jù)驗證方式,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-11-11
Pytorch關于Dataset?的數(shù)據(jù)處理
這篇文章主要介紹了Pytorch關于Dataset?的數(shù)據(jù)處理，學習如何對卷積神經(jīng)網(wǎng)絡編程；首先，需要了解Pytorch對數(shù)據(jù)的使用，也是在我們模型流程中對數(shù)據(jù)的預處理部分，下面我們就一起進入文章查看具體處理過程吧2021-12-12
這篇文章主要介紹了Python 異常的捕獲、異常的傳遞與主動拋出異常操作,結合實例形式詳細分析了Python針對異常捕獲、傳遞、處理等常見操作技巧,需要的朋友可以參考下2019-09-09
這篇文章主要介紹了Python實現(xiàn)打印http請求信息方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-06-06
這篇文章主要介紹了Python3簡單爬蟲抓取網(wǎng)頁圖片代碼實例,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2019-08-08
解決Django migrate No changes detected 不能創(chuàng)建表的問題
今天小編就為大家分享一篇解決Django migrate No changes detected 不能創(chuàng)建表的問題，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-05-05