우아한 파이썬

먼저 간단한 문자열 매칭을 살펴보겠습니다.

텍스트 문자열 s를 고정하고, 패턴 문자열 p를 s의 가장 왼쪽부터 정렬한다고 생각하면 됩니다. 정렬된 부분이 완전히 동일한 경우 일치에 성공하면 실패하면 전체 패턴 문자열 p가 오른쪽으로 1자리 이동되고 정렬 부분이 계속 확인되는 식입니다.

#순진한 일치
def naive_match(s , p):
m = len(s); n = len(p)
for i in range (m-n+1):#Start 포인터 i
if s[i:i+ N] == P: Return true
Return false

KMP 알고리즘에 대해 가장 좋은 점은 Ruan Yifeng의 & lt; 문자열 일치 KMP 알고리즘 & gt;
실제로 패턴 문자열 p는 접미사와 접미사의 부분 일치 테이블을 얻기 위해 전처리됩니다. 즉, kmp = 순진한 일치 + 여러 비트 이동 .
자세한 내용은 Ruan Yifeng의 기사를 참조하세요. 여기서는 확장되지 않습니다.
파이썬 코드 구현은 아래와 같습니다.

def kmp_match(s, p):
m = len(s); n = len(p)
cur = 0#시작 포인터 cur
table = 부분 테이블(p)
while cur<=m-n:
for i in range(n) :
if s[i+cur]!=p[i]:
cur += max(i - table[i-1], 1)# 부분 일치 테이블을 사용하면 1비트만 이동하는 것이 아닙니다. 하지만 한 번에 여러 비트를 이동할 수 있습니다.
break
else:
return True
return False

#Partial match table
def 부분_테이블(p):
'''partial_table("ABCDABD") -> [0, 0, 0, 0, 1, 2, 0]'''
접두사 = set()
postfix = set()
ret = [0]
for i in range(1,len(p)):
prefix.add(p[:i])
postfix = {p[j:i+1] for j in range(1,i+1)}
ret.append(len((prefix&postfix 또는 {''}).pop()))
return ret

print naive_match(" BBC ABCDAB ABCDABCDABDE", "ABCDABD")
print 부분_table("ABCDABD")
print kmp_match ("BBC ABCDAB ABCDABCDABDE", "ABCDABD")