문자열 탐색 - KMP

KMP 알고리즘 >> 무식한 탐색 알고리즘의 개선 버전 만든사람의 앞글자를 따서 KMP 알고리즘이라 불림

김명표 Knuth, Morris, Pratt

무식한 탐색 알고리즘은 시간복잡도가 O( 텍스트 길이*패턴 길이 ) 로 상당히 느린데 

KMP 알고리즘은 O ( 텍스트 길이 + 패턴 길이 )로 굉장히 효율이 좋아짐

성능이 좋은 알고리즘에 속하지만 대부분의 프로그램은 보이어 무어 알고리즘을 채택하고 있다고 한다.

또한 살짝 다른 기능인 자동완성 기능에서는 트라이 자료구조를 사용하여 데이터를 관리하여 보다 빠르게 탐색을 완료한다고 함.


구현 방법 >> KMP 알고리즘은 무식한 탐색 알고리즘에서 중복된 부분을 건너 뛰어서 탐색하여 성능을 향상시킨다.

이미 탐색한 부분을 건너 뛰는 건 당연한 일이다. 하지만 여기서 예외가 발생한다.

ABBABAAAA 에서 ABBABB를 탐색하면
ABBABB       ABBAB 까지는 맞는데 그 다음 B 에서 틀리게 된다.

그러면 

ABBABAAAA
        ABBABB  부터 탐색을 할게 아니라
     ABBABB     AB 부터 탐색해야한다. 이렇게 중복된 부분이 발생하게 된다.

이 부분은 접두어 접미어라는 표현을 사용하게 되는데,

쉽게생각하면 접두어는 머리 두 자를 써서 앞쪽부터, 접미어는 꼬리 미 이니깐 뒤쪽부터 글자를 보면 된다.

위의 상황을 다시보면 중복된 부분의 접두어와 접미어가 겹치는 부분은 AB 이고 접미어까지 밀어주는 예외처리를 해줘야한다.

그렇다면 비교할 패턴의 접두어와 접미어가 겹치는 부분을 확인해야한다. 여기서 패턴의 길이별로 접두어와 접미어를 확인하여 저장해두게된다.



바로 패턴의 길이 별로 접두어와 접미어를 확인하면

ABBABB로 생각하면

A 겹치는 길이 0 >> 접두어 및 접미어는 패턴의 전체 길이와 동일할 수 없다.
AB 겹치는 길이 0 >> 접두어 A 접미어 B
ABB 겹치는 길이 0 >> 접두어 A, AB 접미어 B, BB
ABBA 겹치는 길이 1 (A) >> 접두어 A, AB, ABB 접미어 A, BA, BBA
ABBAB 겹치는 길이 2 (AB) >> 접두어 A, AB, ABB, ABBA 접미어 B, AB, BAB, BBAB
ABBABB  겹치는 길이 3 (ABB) >> 접두어 A, AB, ABB, ABBA, ABBAB 접미어 B, BB, ABB, BABB, BBABB

이렇게 저장되게 된다.