KMP 알고리즘 Python 구현

오늘 KMP 알고리즘을 공부했는데, 여러 언어로 작성된 버전이 많은 것 같은데, 읽을수록. , 그래서 더 헷갈리게 되더라구요. 결국 제가 직접 작성해보았습니다. 요약

먼저 KMP 알고리즘은 문자열 매칭에서 원래의 O(m*n)을 O로 줄이는 최적화 알고리즘입니다. (m+n)

이해를 돕기 위해 먼저 영상을 보시고 아주 명확하게 설명해 주셨네요. 누구나 이해할 수 있는 KMP 문자열 매칭 알고리즘
그렇다면 KMP 알고리즘을 더 잘 이해하고 익히는 방법을 살펴보는 것이 좋습니다. - Yuzi의 답변 - Zhihu Rong
마지막으로 코드에서 패턴 집합 찾기 | 레벨 2 (KMP 알고리즘)
다른 사람의 코드를 너무 많이 읽지 마세요. 많은 사람들이 자신의 코드에 문제가 있다고 생각합니다. 나 자신도 문제에 봉착했을 때 몇몇 동급생이 작성한 코드를 읽고 다른 구덩이로 끌려갔습니다. . . .
마지막으로 코드 re

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

로그인 후 복사

기록