KMP演算法Python實作

今天研究KMP演算法，看來很多版本，有不同的語言寫的，但是感覺越看越亂，最後自己試著寫一份進行總結

#首先，KMP演算法使字串匹配中的最佳化演算法，使原來的O（m*n）降到了O(m n)

關於他的理解，我推薦先看視頻，他講的很清楚了。汪都能聽懂的KMP字串匹配演算法
然後從視覺化方面理解，推薦看看如何更好的理解和掌握KMP 演算法? - 佑子的回答- 知乎容
最後從程式碼層理解Searching for Patterns | Set 2 (KMP Algorithm)
程式碼不要看太多別人的，我感覺好多人寫的也有問題，我在自己運行處問題時，有看有些同學寫的，被帶到其他坑里了。。。
最後記錄程式碼

&#39;&#39;&#39;
先求next数组
&#39;&#39;&#39;def next_list(pattern):
    next=[]
    pattern_list=list(pattern)
    j=0
    i=1
    for s in range(len(pattern)):        #第一位一直是0
        if s==0:
            next.append(0)        #看第i个和第j个字母是否相同，如果相同，则累加
        #同时i,j同时右移
        elif(pattern_list[i]==pattern_list[j]):           
            next.append(j+1)
            j+=1
            i+=1
        #如果不相同，则next为0，同时j也退回第一个位置，i继续前进一个位置
        else:
            next.append(0)
            j=0
            i=s+1
    print(next)    return next

next_list(&#39;ABABCABAB&#39;)      

def kmp(text,pattern):
    #text的位置
    i=0
    #pattern的位置
    j=0
    next=next_list(pattern)    if(not(text and pattern)):
        print(&#39;字符串为空，请输入字符串&#39;)    elif(len(text)<len(pattern)):
        print(&#39;原字符串过小&#39;)    elif(text==pattern):
        print(&#39;字符串一致&#39;)    else:        while( (i<len(text) )):
            print((text[i],pattern[j]))
            print(i,j)            #如果相同，则进行下一个对比
            if( text[i]==pattern[j]):
                i+=1
                j+=1
            #判断是不是匹配完了
            if j==len(pattern):
                print(&#39;从第{0}个位置开始匹配&#39;.format(i-j))
                j=next[j-1]            #如果不匹配，则j反回到前一个字母对应的next
            elif i<len(text) and text[i]!=pattern[j]:                #我就是少了这个判断，一直有问题，就是在不匹配后的第二步，后面这个很关键
                if j!=0:                #这个就是精髓了，如果不匹配，就去找第一个和这个匹配的字符串，然后在这个前面的匹配字符串
                #的后一个字母拿出来，再与长text比较的第i个字母比较
                    j=next[j-1]                #如果j已经回到了0，则通过增加i,text移动到下一个字母
                else:
                    i+=1# text = "ABABDABACDABABCABAB"# pattern = "ABABCABAB"            text=&#39;abxabcabcaby&#39;pattern=&#39;abcaby&#39;kmp(text,pattern)#output:next=[0, 0, 0, 1, 2, 0]


(&#39;a&#39;, &#39;a&#39;)
0 0
(&#39;b&#39;, &#39;b&#39;)
1 1
(&#39;x&#39;, &#39;a&#39;)
2 0
(&#39;a&#39;, &#39;a&#39;)
3 0
(&#39;b&#39;, &#39;b&#39;)
4 1
(&#39;c&#39;, &#39;c&#39;)
5 2
(&#39;a&#39;, &#39;a&#39;)
6 3
(&#39;b&#39;, &#39;b&#39;)
7 4
(&#39;c&#39;, &#39;c&#39;)
8 2
(&#39;a&#39;, &#39;a&#39;)
9 3
(&#39;b&#39;, &#39;b&#39;)
10 4
(&#39;y&#39;, &#39;y&#39;)
11 5
从第6个位置开始匹配

登入後複製

相關建議：

#圖解KMP演算法

######## ######

以上是Python實作字串的KMP演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！