- KMP 알고리즘이란?
- 아이디어 고민
- LPS 배열
- KMP 알고리즘
1. KMP 알고리즘이란?
커누스-모리스-프랫 알고리즘(Knuth–Morris–Pratt algorithm, KMP)은 문자열에서 특정 단어(패턴)을 효율적으로 찾아내는 문자열 검색 알고리즘입니다.
아래 사진과 같이 페이지 검색 기능을 예로 들 수 있습니다.
2. 아이디어 고민
한글자씩 비교하기
비효율적인 방법입니다. 아래 사진에서는 문장이 적지만 수억개의 단어에서 한 단어를 찾으려면 많은 노동이 필요합니다.
시간복잡도는 O(nm)입니다.
O( 찾으려는 문장 * 찾고자하는 단어 )
3. LPS 배열
우선 KMP 알고리즘을 위해 해당 문자의 접두사 접미사가 얼마나 비슷한지 숫자로 나타낸 배열이 있어야 합니다. 그 배열이 LPS 배열입니다.
쉽게 말해 해당 문장의 패턴을 찾을 수 있습니다. LPS 배열을 활용해 효율적인 KMP 알고리즘을 완성할 수 있습니다.
어렵지 않습니다 아래 Step을 따라주세요.
👉 Step 1 ( "aaa"의 LPS 배열 )
j 와 단어 ( "aaa" ) 를 이용해 LPS 배열을 찾아보겠습니다.
Start : 시작
1 : 현재 j 의 위치 문자 : ' a '와 현재 문자 : ' a '를 비교합니다. ( a = a) 같다면 j 를 한 칸 앞( -> )으로 보내줍니다.
1 - 1 : 현재 위치에 j 의 위치를 넣습니다.
2 : 현재 j 의 위치 문자 : ' a '와 현재 문자 : ' a '를 비교합니다. ( a = a) 같다면 j 를 한 칸 앞( -> )으로 보내줍니다.
2 - 2 : 현재 위치에 j 의 위치를 넣습니다.
👉 Step 2
j 와 단어 ( "aab" ) 를 이용해 LPS 배열을 찾아보겠습니다.
1 : 현재 j 의 위치 문자 : ' a '와 현재 문자 : ' b ' 를 비교하여 다르면 j 위치를 j - 1의 LPS 배열 값 : ' 0 ' 으로 해당 단어 : ' a '와 비교합니다
2 : 다르기 때문에 0을 넣어줍니다.
!! 현재 문자와 일치하는 문자가 나타나거나 j 가 0번째 칸으로 갈 때까지 이동합니다. !!
연습
"aaabaaacd" 를 사용하여 연습해 보겠습니다.
[0, 1, 2, 0, 1, 2, 3, 0] 와 같은 LPS 배열을 얻었습니다.
코드
target = "aaabaaac"
# LPS 배열
def getLpsArray (target):
lpsArray = [0]
i = 1
j = 0
while(i < len(target)):
if(target[i] == target[j]): # 같다면 j 를 한 칸 앞( -> )으로 보내줍니다.
j += 1
i += 1
lpsArray.append(j)
else: # 같지 않다면 현재 문자와 일치하는 문자가 나타나거나 j 가 0번째 칸으로 갈 때까지 이동합니다.
if(j > 0):
j -= 1
elif(j == 0):
lpsArray.append(0)
i += 1
return lpsArray4. KMP 알고리즘
원리는 아래 예제를 통해 보여드리겠습니다.
KMP 알고리즘의 시간 복잡도는 O(N+M) 입니다.
O(찾으려는 문장 + 찾고자하는 단어 )
"aabaaabaaabaaac"에서 "aaabaaacd" 를 찾겠습니다.
방법
- 찾으려는 단어를 찾고자 하는 문장에서 1개씩 대조하며 검색합니다.
- 틀린 단어가 나오면 LPS 배열의 -1 위치의 값을 -1 하여 틀린 단어의 전 단어로 이어줍니다.
LPS 배열의 -1 위치의 값 : 1
LPS 배열의 -1 위치의 값 -1 : 0
- LPS 배열의 -1 위치의 값이 0일 경우 틀린 단어 위치로 바로이어줍니다.
LPS 배열의 -1 위치의 값 : 0
전체적인 흐름
전체 코드
# LPS 배열
def getLpsArray (target):
lpsArray = [0]
i = 1
j = 0
while(i < len(target)):
if(target[i] == target[j]): # 같다면 j 를 한 칸 앞( -> )으로 보내줍니다.
j += 1
i += 1
lpsArray.append(j)
else: # 같지 않다면 현재 문자와 일치하는 문자가 나타나거나 j 가 0번째 칸으로 갈 때까지 이동합니다.
if(j > 0):
j -= 1
elif(j == 0):
lpsArray.append(0)
i += 1
return lpsArray
# KMP 알고리즘
def kmpSearch(text, target, lpsArray):
i = 0
j = 0
isFind = False
while i < len(text):
if (text[i] == target[j]):
i += 1
j += 1
else:
if (j != 0):
j = lpsArray[j-1]
else:
i += 1
if ( j == len(target) ):
isFind = True
return i - j
if(not isFind):
return -1
def main():
target = "aaabaaac"
text = "aabaaabaaabaaac"
lpsArray = getLpsArray(target)
print(kmpSearch(text, target, lpsArray))
if __name__ == '__main__':
main()
출력 : 7
참고 사이트
