[알고리즘/ 파이썬] KMP 알고리즘 알아보기

KMP 알고리즘(Knuth-Morris-Pratt algorithm)이란 문자열 검색을 매우 빠르게 해주는 알고리즘이다.

특정 패턴이 주어졌을 때 전체 문자열을 빠르게 검색하여 그 패턴이 어디에 등장하는 지 찾아준다.

KMP 알고리즘을 이해하려면 파이 배열에 대해 알아야 한다.

파이 배열의 i번째 성분은, 문자열의 i번째까지의 부분 문자열에서 접두사, 접미사가 같아지는 최대 길이를 뜻한다.

파이 배열의 예시는 아래와 같다.

KMP 알고리즘은 2단계에 걸쳐 실행된다.

1. 주어진 패턴에 대해 파이 배열 만들어내기

2. 파이 배열을 활용하여 패턴의 등장 위치를 빠르게 찾아내기

1. 파이 배열 만들기

파이 배열의 0번째 값은 무조건 0이 된다. 한글자 짜리 문자열에는 접두사, 접미사가 없기 때문이다.

파이 배열을 구하는 데에는 두 개의 포인터가 사용된다. 이를 i, j라 하자.

i는 현재 어디까지 일치하는지 표시하는 포인터고 j는 탐색 위치를 표시하는 포인터 역할을 한다.

처음에 i는 0, j는 1로 초기화 되어있다. j가 0에서 시작하지 않은 이유는 아까 말했듯이 pi[0]=항상 0이기 때문이다.

흐름은 대략 다음과 같다.

pattern이 주어졌을 때, pattern[i]와 pattern[j]를 비교한다.

같으면? => i와 j 둘다 +1을 해줌. pi[j]에는 i값을 저장한다.

다르면? => i를 pi[i-1]로 변경

사실 이 설명만으론 이해하기 힘들고, 글보다는 영상으로 또는 직접 코드를 돌려보면서 깨달음을 얻어야 한다.

여기서는 왜 i가 pi[i-1]로 변경되어야 하는지만 설명하고 넘어간다.

한마디로 동일성이 보장되는 구간을 최대한 찾음으로써 쓸데없는 반복을 줄이고 빠르게 파이 배열을 구해내는 것이다.

파이 배열을 구하는데 소요되는 시간은 O(N)이다.

파이썬 코드 <= 꼭 직접 연구하자!!

pattern = 'ababbab'

#  kmp_table
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 = table[i-1]

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

print(table)

출력 결과

[0, 0, 1, 2, 0, 1, 2]

2. 파이 배열을 활용하여 KMP 알고리즘

KMP 알고리즘은 파이 배열을 구하는 방법과 상당히 유사하게 진행된다.

이번에도 두 개의 포인터 i, j가 등장한다. 두 포인터 모두 0으로 초기화된다.

i는 패턴을 탐색하는 포인터, j는 전체 문자열을 탐색하는 포인터다.

흐름은 대략 다음과 같다.

패턴[i]와 전체문자열[j]를 비교한다.

같으면? => i, j 모두 +1을 해주고 만약 i의 값이 len(패턴)이 되었으면 원하는 패턴을 찾았다는 의미이므로 이를 결과에 저장해준다.

다르면? => i를 pi[i-1]로 변경

이 설명 역시 글만으로는 이해가 힘들고 직접 코드를 분석해봐야 한다. 나도 많이 헤맸지만 아래와 같은 그림을 직접 그려보고 나서야 감이 잡혔다. 아래 그림들은 왜 i값을 pi[i-1]로 변경해주는 지에 대한 이유다.

위의 그림은 왜 KMP 알고리즘이 탐색 시간을 획기적으로 줄일 수 있는 지 알려준다.

파이배열을 활용하여 동일성이 보장되는 구간을 빨리 뛰어넘는 것이다.

전체 파이썬 코드

def kmp(all_string, pattern):
    #  kmp_table
    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 = table[i-1]

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

    #  kmp
    result = []
    i = 0
    for j in range(len(all_string)):
        while i > 0 and pattern[i] != all_string[j]:
            i = table[i-1]

        if pattern[i] == all_string[j]:
            i += 1
            if i == len(pattern):
                result.append(j - i + 1)
                i = table[i-1]

    return result

print(kmp('xabxxbaxbaxbaxbaxabxbaxbabx', 'abx'))
print(kmp('abababab', 'abab'))

출력 결과