알고리즘 악 보 일기 - KMP 알고리즘 python 구현
KMP 알고리즘 이 무엇 인지 에 대해 서 는 대 신의 블 로 그 를 보 세 요. 완 일 봉 - 문자열 에 맞 는 KMP 알고리즘 막 귀 막 을 너무 잘 썼 습 니 다. 하지만 그 가 말 한 부분 은 표 의 아래 표 와 각 참고서 가 어 울 리 지 않 습 니 다.응시 수 요 를 위해 서 내 가 이해 하 는 next 배열 로 바 뀌 었 다.
KMP 알고리즘 - NEXT 배열
이것 은 숙제 문제 입 니 다. S = "abcaabbabcabaacbacba" 실효 함수 의 값 [- 1, 0, 0, 0, 1, 1, 2, 0, 1, 2, 3, 4, 2, 1, 1, 0, 0, 0, 0] 을 구 합 니 다. 물론 이것 은 너무 길 어서 우리 가 명 S = "abcdabcy" 를 설명 하 는 데 불편 합 니 다. 그러면 실효 편지 수 를 손 으로 쓰 려 면 첫 번 째 는 "- 1" 이 고 abcd 는 반드시 - 1000, 두 번 째 a 가 나타 날 것 입 니 다.이 때 는 0 이 고, 그 다음 bc 는 12 이 며, y 는 3 에 대응한다.있 습 니 다. [- 1, 0, 0, 0, 1, 2, 3]
그럼 프로그램 으로 이 루어 지면 요?
def pipeizhi(p):
# abcdabcy
# next next[]:-1 0 0 0 0 1 2 3
j = 0
k = -1
next = [-1]
for i in range(1, len(p)):
next.append(0) # next [-1,0,0,0...]
try:
while (j < len(p) - 1):
if k == -1 or p[j] == p[k]:
# ， 。j ， k 。
j += 1
k += 1
next[j] = k
else:
k = next[k]
except IndexError:
print next, k, j #
return nextKMP 알고리즘 구현
이제 next 배열 이 있 으 면 하고 싶 은 대로 할 수 있 습 니 다.
def KMP(s, t): #s ，t
slen = len(s)
tlen = len(t)
if slen >= tlen:
i = 0
j = 0
next = pipeizhi(t)
# print next
while i < slen: #
print [i,j]
if j == -1 or s[i] == t[j]:
#i ，j 。
i += 1
j += 1
else:
j = next[j]
if j == tlen:
return i - tlen
return -1 #-1 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
