이 문서의 예에서는 Python의 문자열에 대한 KMP 알고리즘 구현을 설명합니다. 참고하실 수 있도록 자세한 내용은 다음과 같습니다.
오늘 KMP 알고리즘을 공부했는데, 여러 언어로 작성된 버전이 많은 것 같은데, 읽을수록. , 그래서 더 헷갈리게 되더라구요. 결국 제가 직접 작성해보았습니다. 요약
먼저 KMP 알고리즘은 문자열 매칭에서 원래의 O(m*n)을 O로 줄이는 최적화 알고리즘입니다. (m+n)
이해를 돕기 위해 먼저 영상을 보시고 아주 명확하게 설명해 주셨네요. 누구나 이해할 수 있는 KMP 문자열 매칭 알고리즘
그렇다면 KMP 알고리즘을 더 잘 이해하고 익히는 방법을 살펴보는 것이 좋습니다. - Yuzi의 답변 - Zhihu Rong
마지막으로 코드에서 패턴 집합 찾기 | 레벨 2 (KMP 알고리즘)
다른 사람의 코드를 너무 많이 읽지 마세요. 많은 사람들이 자신의 코드에 문제가 있다고 생각합니다. 나 자신도 문제에 봉착했을 때 몇몇 동급생이 작성한 코드를 읽고 다른 구덩이로 끌려갔습니다. . . .
마지막으로 코드 re
'''
先求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('字符串为空，请输入字符串') elif(len(text)<len(pattern)):
print('原字符串过小') elif(text==pattern):
print('字符串一致') 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('从第{0}个位置开始匹配'.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='abxabcabcaby'pattern='abcaby'kmp(text,pattern)#output:next=[0, 0, 0, 1, 2, 0]
('a', 'a')
0 0
('b', 'b')
1 1
('x', 'a')
2 0
('a', 'a')
3 0
('b', 'b')
4 1
('c', 'c')
5 2
('a', 'a')
6 3
('b', 'b')
7 4
('c', 'c')
8 2
('a', 'a')
9 3
('b', 'b')
10 4
('y', 'y')
11 5
从第6个位置开始匹配 기록
관련 권장 사항:
위 내용은 Python은 문자열에 대한 KMP 알고리즘을 구현합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!