KMP 알고리즘

KMP 알고리즘은 빠른 문자열 검색을 돕는 알고리즘이다.

 

찾고자 하는 문자열을 pattern 이라고 하고

모든 문장을 all string 라고 하자.

 

KMP 알고리즘을 구현하기 위해 해야할 것이 있다.

1. Pattern 문자열을 이용해 pi(파이)배열을 만들어야 한다.

2. pi 배열을 이용해 빠른 문자열을 검색해준다.

 

pi배열 이란, Pattern 문자열에 있는 접두사 (Prefix) 와 접미사 (Suffix)가 같아

지는 최대 길이를 나열해 놓은 배열이다.

말로 설명하지니 좀 어려우므로 아래 그림을 통해 확인해보자.

예를 들어, pattern이 "abcdabc" 라면 단어의 길이가 7인데,

1개씩 늘려가며 접두사와 접미사가 겹치는 최대 길이를 나타내 보면,

pi배열은 [0, 0, 0, 0, 1, 2, 3]이 된다.

 

이 pi배열의 역할은 KMP 알고리즘에 핵심적인 역할을 하는데, 문자열을 비교할 때, 동일성이 보장되는 구간을 찾으므로 쓸데없는 반복을 바로 넘길 수 있다는 것이다.

 

 

아래는 파이썬 코드를 이용해 pi 배열을 구하는 방법이다. 직접 코드를 짜면서 천천히 이해해 보도록 하자.

pattern = 'abcdabc'
pi_table = [0 for _ in range(len(pattern))]

i = 0
for j in range(1, len(pattern)):

    while i > 0 and pattern[i] != pattern[j]:	
        i = pi_table[i-1]
        
    if pattern[i] == pattern[j]:
        i += 1
        pi_table[j] = i

print(pi_table)

pi 배열을 이용해 이제 문자열 검색을 해보도록 하자.

pi 배열을 만드는 알고리즘과 비슷하게 kmp 알고리즘도 구현된다.

 

all_string = 'abcdabcdabcdabcababc'

i = 0
for j in range(len(all_string)):
    
    while i > 0 and pattern[i] != all_string[j]:
        i = pi_table[i-1]
    
    if pattern[i] == all_string[j]:
        i += 1
        if i == len(pattern):
            i = pi_table[i-1]
            print('FIND')

전체코드

pattern = 'abcdabc'
pi_table = [0 for _ in range(len(pattern))]

i = 0
for j in range(1, len(pattern)):
    
    while i > 0 and pattern[i] != pattern[j]:
        i = pi_table[i-1]
        

    if pattern[i] == pattern[j]:
        i += 1
        pi_table[j] = i

print(pi_table)

all_string = 'abcdabcdabcdabc'

i = 0
for j in range(len(all_string)):
    
    while i > 0 and pattern[i] != all_string[j]:
        i = pi_table[i-1]
    
    if pattern[i] == all_string[j]:
        i += 1
        if i == len(pattern):
            i = pi_table[i-1]
            print('FIND')

동영상 참고: https://www.youtube.com/watch?v=cH-5KcgUcOE 

+ 코드와 그림과 말로는 이해가 잘 되지 않는 부분들이 많다.

동영상으로 어떻게 움직이는데 본다면 이해되는데, 도움이 많이 될 것 같다.