Python implementiert den KMP-Algorithmus für Strings

Das Beispiel in diesem Artikel beschreibt den KMP-Algorithmus für die String-Implementierung in Python. Teilen Sie es als Referenz mit allen. Die Details lauten wie folgt:

Python-Implementierung des KMP-Algorithmus

Ich habe den KMP-Algorithmus heute studiert. Es scheint, dass dort Es gibt viele Versionen in verschiedenen Sprachen, aber je mehr ich mir das ansah, desto verwirrender wurde es. Schließlich habe ich versucht, eine Zusammenfassung zu schreiben Schließlich ist der KMP-Algorithmus ein Optimierungsalgorithmus beim String-Matching, daher wurde das ursprüngliche O(m*n) auf O(m+n) reduziert

In Bezug auf sein Verständnis empfehle ich, zuerst das Video anzusehen. er hat es sehr deutlich erklärt. Der KMP-String-Matching-Algorithmus, den jeder verstehen kann

und ihn dann aus visueller Sicht verstehen kann. Es wird empfohlen, den KMP-Algorithmus besser zu verstehen und zu beherrschen. - Yuzis Antwort - Zhihu Rong
Schließlich verstehen Sie die Suche die Codeebene für Muster |. Set 2 (KMP-Algorithmus)

Lesen Sie nicht zu viele Codes anderer Leute. Ich habe das Gefühl, dass die Codes vieler Leute auch Probleme haben und wurde in andere Gruben gebracht. . .

Zuletzt aufgezeichneter Code

                                                                                  

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

Detaillierte Erläuterung des KMP-Algorithmus

Verständnis der schwierigsten Teile des KMP-Algorithmus

Prinzip und Implementierung des KMP-Algorithmus

Illustrierter KMP-Algorithmus

Das obige ist der detaillierte Inhalt vonPython implementiert den KMP-Algorithmus für Strings. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!