문자열매칭
문자열매칭
개념 공부는 동비나 유투브를 참조해서 공부하면 좋습니다.
문자열매칭 1 (KMP 알고리즘; Knuth-Morris-Pratt)
문서 내에서 원하는 문자열의 위치를 찾습니다.
- 접두사와 접미사를 사용해서 진행합니다.
- 문자열 매칭에 실패하면 얼마나 점프할건지에 대한 정보를 저장하여 검색 횟수를 줄이는게 목표입니다.
def kmp(text, pattern):
n, m = len(text), len(pattern)
# 접두사와 접미사가 일치하는 위치를 계산합니다
lps = compute_lps(pattern)
# 패턴 문자열과 텍스트 문자열을 비교합니다
i, j = 0, 0
while i < n:
# 겹치면 둘다 진행
if pattern[j] == text[i]:
i += 1
j += 1
# 겹치는 부분이 패턴의 길이와 같다면 해당 인덱스를 출력한다.
if j == m:
return i - j
# 겹치는 부분이 끝났을 때 lps에 계산된 정도만 이동한다.
elif i < n and pattern[j] != text[i]:
if j != 0:
j = lps[j-1]
else:
i += 1
return -1
def compute_lps(pattern):
m = len(pattern)
# 접두사와 접미사가 일치하는 위치를 저장할 리스트를 초기화합니다
lps = [0] * m
len_lps = 0
i = 1
while i < m:
# 겹치면 다음 문자도 같이 확인
if pattern[i] == pattern[len_lps]:
len_lps += 1
lps[i] = len_lps
i += 1
# 겹치는게 끝나면 겹치기 시작했던 바로 그 전값으로 시작 001123에서 끝났으면 123 전의 1에서 시작
# 이때, i는 변하지 않고
elif len_lps != 0:
len_lps = lps[len_lps-1]
else:
# 겹치지 않고 len_lps도 0이라면 처음부터 일치하는 문자열을 또 찾아야한다.
lps[i] = 0
i += 1
return lps
- 알고리즘
- 접미사와 접두사가 일치하는 위치를 계산한다. ( compute_lps )
- 접두사와 접미사가 일치하는 위치를 저장할 리스트를 초기화합니다.
- 겹치면 다음 문자도 같이 확인합니다.
- 겹치는게 끝나면 겹치기 시작했던 바로 그 전 값으로 시작, 001123에서 끝났으면 123 전의 1에서 시작
- 이때, i는 변하지 않는다. (기존 문자열을 가리키는 값)
- 겹치지 않고 len_lps도 0이라면 처음부터 일치하는 문자열을 또 찾아야한다.
- 패턴 텍스트 문자열을 비교한다.
- 겹치는 부분이 패턴의 길이와 같다면 해당 인덱스를 출력한다.
- 겹치는 부분이 끝났을 때 lps에 계산된 정도만 이동한다.
- 접미사와 접두사가 일치하는 위치를 계산한다. ( compute_lps )