문자열 검색 알고리즘
참고 ) 만약 브루트포스(완전탐색)를 통해 문자열 패턴을 찾아낸다면?
EX : ABCABBBCAAACB 문자열에서 AB 패턴을 찾기
•
인덱스 0에서 시작 : AB → 패턴 매칭 O
•
인덱스 1에서 시작 : BC → 패턴 매칭 X
•
인덱스 2에서 시작 : CA → 패턴 매칭 O
이처럼 브루트포스를 통해 전체 문자열에서 패턴을 찾아내려고 하면 O(N * M)의 시간복잡도가 소요. 그렇기에 모든 경우를 비교하지 않아도 패턴을 찾아낼 수 있는 KMP 알고리즘을 사용할 필요가 있음
KMP 알고리즘의 핵심
•
패턴의 접두사 & 접미사 개념을 활용해 반복되는 연산을 얼만큼 건너뛸 수 있는지에 대해 집중
패턴 내 존재하는 접두사 & 접미사가 일치한다면 접미사를 접두사로 다시 바라봄을써 문자열 탐색을 이어 진행할 수 있기 때문
1.
LPS 배열(Longest Prefix Suffix) 생성
lps[i] = P[0,…,i]까지의 부분 문자열에서 접두사 = 접미사인 최대 길이
2.
텍스트를 순회하며 패턴과 비교
3.
불일치 발생시, LPS를 이용해 패턴의 이동 거리 결정
EX : 패턴(ABABCABAB), LPS 배열([0, 0, 1, 2, 0, 1, 2, 3, 4])
•
lps[4] = 0 : 인덱스 4까지의 부분 문자열 ABABC에서 접두사 = 접미사인 최대길이는 0
•
lps[8] = 4 : 부분 문자열 ABABCABAB에서 접두사 ABAB가 접미사와 일치
코드
# LPS 배열을 만드는 함수
def compute_lps(pattern):
lps = [0] * len(pattern) # 부분 문자열에서 (접두사 = 접미사)인 최대 길이
matched_prefix_length = 0 # 이전까지 일치한 접두사 길이
i = 1 # 첫 번째 문자는 무조건 lps[0]=0 이므로 인덱스 1부터 시작
while i < len(pattern):
# 현재 글자가 length 위치의 글자와 동일한 경우
if pattern[i] == pattern[matched_prefix_length]:
matched_prefix_length += 1
lps[i] = matched_prefix_length # i번째까지의 최대길이 갱신
i += 1
else:
# 불일치긴 하지만, 현재까지 일치한 접두사 길이가 0이 아닌 경우
if matched_prefix_length != 0:
matched_prefix_length = lps[matched_prefix_length - 1]
else:
# 불일치이고, 지금까지 (접두사 = 접미사)인 게 없었다면
lps[i] = 0
i += 1
return lps
def kmp_search(text, pattern):
lps = compute_lps(pattern) # 패턴의 "접두사 = 접미사"인 최대 길이 테이블
i = 0 # i는 text index : 현재 텍스트 인덱스
j = 0 # j는 pattern index : 패턴 길이
results = [] # "텍스트에서 패턴이 매칭된 시작위치(i-j)"가 원소
while i < len(text):
# 현재 텍스트의 문자열과 패턴의 문자열이 동일한 경우
if text[i] == pattern[j]:
# 두 인덱스 모두 증가
i += 1
j += 1
# 매칭이 끝난 경우(j인덱스가 끝에 도달)
if j == len(pattern):
results.append(i - j)
j = lps[j -1]
else:
# 불일치 경우
if j != 0:
# j 인덱스가 0이 아닌 경우(패턴 시작 위치가 아닌 경우) :
j = lps[j-1]
else:
# 패턴의 시작 인덱스에서도 불일치 : 텍스트만 한 칸 이동
i += 1
return results
# 실행 예시
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
print(kmp_search(text, pattern)) # [10]
Python
복사
KMP 알고리즘의 시간복잡도
•
시간복잡도 : O(N + M)
◦
N = 텍스트 길이
▪
kmp_search(text, pattern) 함수에서 텍스트와 패턴을 비교하면서 불일치하는 경우 j를 뒤로 점프했음. 이 과정에서 최대 N만큼 비교할 수 있으므로 O(N)
◦
M = 패턴 길이
▪
compute_lps(pattern) 함수에서 패턴의 접두사-접미사 일치 길이를 구하기 위해 패턴 길이 M에 대해 한 번씩 이동하며 비교했으므로 O(M)
즉, KMP는 이미 맞은 부분은 재검사하지 않아 불필요한 반복이 없음
참고 자료
