Python implémente l'algorithme KMP pour les chaînes

L'exemple de cet article décrit l'algorithme KMP pour l'implémentation de chaînes en Python. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

Implémentation Python de l'algorithme KMP

J'ai étudié l'algorithme KMP aujourd'hui. Il existe de nombreuses versions écrites dans différentes langues, mais plus je le regardais, plus cela devenait confus, alors j'ai finalement essayé d'écrire un résumé

D'abord. avant tout, l'algorithme KMP est un algorithme d'optimisation dans la correspondance de chaînes, donc l'original O(m*n) a été réduit à O(m+n)

Concernant sa compréhension, je recommande de regarder d'abord la vidéo, il l'a expliqué très clairement. L'algorithme de correspondance de chaînes KMP que tout le monde peut comprendre
puis le comprendre sous l'aspect visuel. Il est recommandé de voir comment mieux comprendre et maîtriser l'algorithme KMP - Réponse de Yuzi - Zhihu Rong
Enfin, comprendre la recherche à partir de ? le niveau de code pour les modèles | Ensemble 2 (algorithme KMP)
Ne lisez pas trop les codes des autres. J'ai l'impression que les codes de beaucoup de gens ont aussi des problèmes. Lorsque j'ai moi-même rencontré des problèmes, j'ai lu les codes écrits par certains camarades de classe. et a été emmené dans d'autres fosses. . .
Dernier code enregistré

'''
先求next数组
'''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('ABABCABAB')      

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

                                                                                  

Explication détaillée de l'algorithme KMP

Compréhension des parties les plus difficiles de l'algorithme KMP

Principe et mise en œuvre de l'algorithme KMP

Algorithme KMP illustré

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!