KMP 알고리즘이란?
기존의 브루트포스 방식의 문자열 검색의 시간 복잡도인 O(NM) 의 비효율성을 생각하여 만들어진 알고리즘으로 KMP 알고리즘의 시간 복잡도는O(N+M) 으로 매우 빠른 성능을 보여줍니다. KMP 알고리즘에서는 먼저 접두사, 접미사의 개념과 Pi 배열의 개념을 알고 있어야 합니다.
한 줄 요약 : 문자열 검색에 KMP 알고리즘이 빠름!
🔨 접두사와 접미사
일반 국어 시간에도 많이 나왔던 접두사와 접미사는 코딩 세계에서 예시를 들자면,
banana의 접두사 : b,ba,ban,bana, banan, banana
bananan의 접미사 : a, na, ana, nana, anana, banana
가 있습니다.
🔨 Pi 배열
Pi 배열은 p[i] 에서 주어진 문자열 0~ i 까지의 부분 문자열 중에서 접두사 == 접미사 가 될 수 있는 문자열 중에서 가장 긴 것의 길이를 담는 배열입니다. 무슨 말인지 당최 모르는게 당연합니다. 저도 그랬으니까요..
예시를 들어볼까요?
문자열
ABAABAB의 pi 배열
p[0] = A = 0
p[1] = AB = 0
p[2] = ABA = 1 // A
p[3] = ABAA = 1 // A
p[4] = ABAAB = 2 // AB
p[5] = ABAABA = 3 // ABA
p[6] = ABAABAB = 2 // AB
약간 느낌이 오시나요? 즉 접두사와 접미사가 최대로 같은 접두사 or 접미사의 길이를 담은 배열입니다!
이제 준비는 끝났으니 본격적으로 KMP 알고리즘에 대해 알아보도록 하겠습니다.
KMP 알고리즘
이제 위의 두 개념을 어떻게 사용할지 생각해 봅시다. 예를들어 ABCDABCDABEE 에서 ABCDABE를 찾을때 어떻게 할까요?
단순한 방법으로 검색을 한다면 아래의 두 사진과 같이 진행이 될 것입니다.
일반적인 검색은 6번 인덱스의 틀린 사실에 중심을 두는 것 보다,
박스 친 부분의 일치 한다는 사실을 이용하여 검색을 획기적으로 개선하는 것이 KMP 알고리즘 입니다.
그렇다면 어떻게 이용할까요? 아래와 같이 접두사, 접미사가 같기 때문에 4,5 번 인덱스에서 패턴을 시작해도 됩니다!!
( 👇 중간 단계 껑충 스킵 )
이렇듯 KMP 알고리즘은 일치했던 배열에 주목해 Pi 배열을 이용해 많은 중간 시도를 건너뛸 수 있습니다!
코드
# 문자열 매칭 알고리즘
## 단순 비교 알고리즘 보다 짧은 시간 복잡도를 지님.
### 접두사와 접미사의 개념으로 일치하는 경우에 점프를 수행해서 연산 줄여줌
def makeTable(pattern): # Pi 테이블
patternSize = len(pattern)
table = [0] * patternSize # 테이블 초기화
j = 0 # 첫 인덱스
for i in range(1,patternSize):
while j > 0 and pattern[i] != pattern[j] : # 처음 j 인덱스 값과 같은 i 찾기
j = table[j-1] # 없으면 이전최대값 넣음
if pattern[i] == pattern[j]: # 같은 것 찾으면
j += 1
table[i] = j
return table # 접두사 접미사 최대 길이 테이블
def KMP(parent,pattern):
table = makeTable(pattern)
parentSize = len(parent)
patternSize = len(pattern)
j = 0
for i in range(parentSize):
# 주어진 정보로 최대한 중간 단계를 뛰어 넘기 위해서
while j > 0 and parent[i] != pattern[j]:
# Pi 배열을 이용해 중간 단계 건너뜀
j = table[j-1]
if parent[i] == pattern[j]:
if j == patternSize -1:
print("1")
j = table[j]
break
else:
j+=1
print("0")
print(KMP("abacaabaabacaaba","abacaaba"))