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个位置开始匹配

登录后复制