KMP 알고리즘이란?

KMP Algorithm

KMP 알고리즘이란?

KMP(Knuth-Morris-Pratt) 알고리즘은 어떤 문자열에서 특정 문자열을 찾고자 할때 유용한 알고리즘입니다.
KMP 란 이름이 붙은 이유는 Knuth, Morris, Pratt 세사람이 함께 만들어냈기 때문이라 합니다.

KMP 알고리즘을 살펴보기전에 어떤 문자열에서 특정 문자열을 찾고자 한다면 어떻게 해야할까?
단순히 두 문자열을 앞에서부터 차례대로 비교해 나아가면 된다. 효율적이진 않지만 매우 직관적이며 간단합니다.

단순 비교 알고리즘

원본문자열과 찾을 문자열은 다음과 같습니다.

원본 문자열 : "abcdef"
찾을 문자열 : "cd"

찾을 문자열이 원본문자열에 있을지 판단하는 과정은 다음과 같이 진행됩니다.

쉽고 단순하게 찾을 수 있지만 O(M*N)의 시간복잡도를 가지게 됩니다. (N : 원본 문자열의 길이, M : 찾을 문자열의 길이)
그렇다면 우리가 살펴볼 KMP 알고리즘은 어떨까요??

KMP 알고리즘

KMP 알고리즘의 핵심은 이전까지 비교햤던 정보를 기억하는 것 입니다.
접두사와 접미사를 활용해서 일정 부분이 맞는다면 Jump 하는 방식입니다.
그러기 위해서는 문자열이 일치하지 않았을 경우의 어디로 Jump 할지에 대한 Table이 필요합니다.
비교가 실패했을 때 사용할 Table을 만드는 함수를 Failure Function(실패함수)라고 합니다.

실패함수를 통해서 만들어지는 Table에는 해당 인덱스 까지 왔을 때의 최대 일치길이 정보를 포함하고 있습니다.
즉, 비교하다가 틀렸을 경우에 어디까지 일치했는지를 확인하고 Jump 해서 다시 비교를 진행하게 됩니다.
보다 쉬운 이해를 위해서 예시를 통해서 KMP 알고리즘의 과정을 살펴보겠습니다.

원본 문자열 : ababacabacaabacaaba
찾을 문자열 : abacaaba

• 먼저 찾을 문자열에 대해 실패함수 Table을 생성한다.(i: 원본 문자열 index, j : 찾을 문자열 index)

• 원본 문자열과 비교하면서 일치하는지 확인한다.

• 일치할 경우

    i += 1   
        j += 1   

• 불일치할 경우

    j = table[j-1]
    이전까지 일치한 경우에 대해서 Jump 하는 과정입니다.        

• 변경된 j 값을 기준으로 다시 비교를 진행한다.

KMP 알고리즘을 사용하면 O(M+N)의 시간복잡도만으로 문자열 내에서 특정 문자열을 검색 해 낼 수 있습니다.
그렇다면 실패함수는 어떻게 구현할까요?

Failure Function(실패함수)

실패함수는 문자열 내에서 최대일치길이 정보를 저장하고 있습니다.
최대일치길이란 (길이 ~ 특정 인덱스) = (0 ~ 길이)를 의미합니다.
실패함수 Table은 다음과 같은 과정을 통해서 만들어집니다.

• 찾고자 하는 단어와 동일안 길이의 영배열을 만든다. -> 추후 실패함수 Table

• j = 0, i = 1 두 인덱스 변수를 생성한다.

• i, j 위치에 있는 문자들을 비교한다.

• 일치할 경우

    j += 1   
    table[i] = j   
    i += 1   

• 불일치할 경우

    if j > 0  {
        j = table[j-1]
    }

• 비교하는 과정을 끝까지 계속한다.

실패함수를 만드는 과정을 예시로 살펴보면 다음과 같습니다.

이렇게 실패함수를 생성하고 KMP 알고리즘을 적용시키면 문자열에서 특정 문자열을 찾을때 훨씬 빠른 속도로 탐색 할 수 있습니다.

Python으로 작성된 예시자료는 다음 링크에 있습니다.
예시코드 보기

정리하면서

문자열에서 특정 문자열을 탐색할 경우 단순한 비교만 사용해서 진행했었다.
실제 사용자 환경에서도 단순한 비교 알고리즘을 사용했다면 시스템에 굉장한 부하가 걸렸을 것이라 생각된다.
KMP 알고리즘 이외에도 다양한 탐색 알고리즘이 존재할 것이라 생각되고 개발자가 되기 위해서 더욱 열심히 공부해야 겠다.

참조한 자료

https://blog.naver.com/ndb796/221240660061
https://jason9319.tistory.com/130