Python如何實(shí)現(xiàn)KPM算法

這篇文章主要介紹Python如何實(shí)現(xiàn)KPM算法，文中介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們一定要看完！

知識(shí)點(diǎn)說明：

先說前綴，和后綴吧

比如有一個(gè)串：abab

則在下標(biāo)為3處的（前綴和后綴都要比下標(biāo)出的長(zhǎng)度小1，此處下標(biāo)為3出的長(zhǎng)度是4）

前綴為：a,ab,aba

后綴為：b,ba,bab

一、要獲取KPM算法的next[]數(shù)組

簡(jiǎn)單說一下原理吧，首先k，用來存放前綴的下標(biāo)，首先初始化j=0（j用來表示模式串的下標(biāo)，一直去模式串的每一位與前面的進(jìn)行比較，如果相等，則記錄下當(dāng)前位置與前面的哪個(gè)位置相同，我們這里主要是要記錄相同位置的下一個(gè)位置，就是不相同的位置，從不相同的位置開始比較，就是回溯到不相同位置，所以這里在t[j]==t[k]成立的時(shí)候要j+1，為了比較下一個(gè)位置是否相同，k也要+1），模式串從0開始，k=-1，next[0]=-1第一個(gè)位置賦默認(rèn)值-1；

此處串采用=“abab”

第一次循環(huán)：

判斷k是否等于-1，如果等于則，j和k都+1，

此時(shí)j=1，k=0，next[1]=0，也就是第2個(gè)位置（下標(biāo)1）的回溯位置還是0，因?yàn)榍熬Y的最大長(zhǎng)度必須小于當(dāng)前位置的長(zhǎng)度；

第二次循環(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

此時(shí)next=[-1,0,0,1]，next[3]=1表示在next[3]處發(fā)生不匹配時(shí)，也就是模式串下標(biāo)為3時(shí)為“b”，說明前面aba都是和目標(biāo)串都匹配，所以模式串不匹配位置前面的串a(chǎn)ba一定與目標(biāo)串不匹配位置前面的前3個(gè)值相等，也就是aba，所以此刻，只需要回溯到模式串的1位置，也就是模式串的b，模式串b前面是a，滿足目標(biāo)串的前一個(gè)a。

第五次循環(huán)：

k依舊是不等于-1，就是比較上一個(gè)位置后面的兩個(gè)數(shù)再進(jìn)行比較，簡(jiǎn)單的說，以此取出每一項(xiàng)與第一項(xiàng)比較，如果存在相等的就再比較下一個(gè)與第二項(xiàng)是否相等。

代碼如下：

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 或者 開始位置和結(jié)尾位置有相同的元素
            j, k = j + 1, k + 1  # j和k都加1,當(dāng)前位匹配，則從下一個(gè)位置開始匹配，所以k+1；j再進(jìn)行取下一位判斷是否也是匹配，所以也要+1
            next[j] = k  # 當(dāng)前位置要取k項(xiàng)
        else:#如果不相等，再把k置-1，下一次循環(huán)再進(jìn)行+1操作，j這個(gè)位置再存入0，表示無匹配項(xiàng)
            k = next[k]
    return next

二、KMP函數(shù)

原理和BF算法是一樣的，唯獨(dú)不同的是，當(dāng)模式串與目標(biāo)串不匹配的時(shí)候，不直接回溯模式串，而是根據(jù)模式串的next[]表，查詢要回溯到的位置，直接回溯到模式串的指定位置，KMP算法的核心也就在這里，但是這種方法一般只對(duì)前綴和后綴存在相同元素時(shí)，有效果，也就是說相同部分是一樣的就不再進(jìn)行比較了，從相同元素的下一個(gè)位置開始比較，所以KMP算法最復(fù)雜的部分其實(shí)就是找next[]表，要找出模式串的每一個(gè)位置，是否有相同前綴，如果有則標(biāo)注該相同位置，下次回溯就不用回溯到0這個(gè)位置，可以從不相同位置開始。

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 或者 開始位置和結(jié)尾位置有相同的元素
            j, k = j + 1, k + 1  # j和k都加1,當(dāng)前位匹配，則從下一個(gè)位置開始匹配，所以k+1；j再進(jìn)行取下一位判斷是否也是匹配，所以也要+1
            next[j] = k  # 當(dāng)前位置要取k項(xiàng)
        else:#如果不相等，再把k置-1，下一次循環(huán)再進(jìn)行+1操作，j這個(gè)位置再存入0，表示無匹配項(xiàng)
            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)

結(jié)果：

以上是“Python如何實(shí)現(xiàn)KPM算法”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對(duì)大家有幫助，更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！