문자열 검색 알고리즘(KMP)

1. 개념

KMP 알고리즘은 문자열 검색 알고리즘으로 알고리즘을 만든 사람의 이름 Knuth, Morris, Prett의 글자를 와서 이름이 붙었다.

우선 이 알고리즘을 왜 사용하는지를 보기 위해 단순한 문자열 검색의 예를 들어보겠다.

문자열 abcdefghijklmnop 이 있을때 ghi 문자열을 찾아보자. 단순하게 검색한다면 다음과 같이 검색할 것이다.

     abcdefghijklmnop        

(1) ghi

(2)  ghi

(3)    ghi

.

.

.

이런 식으로 한 자리씩 이동하면서 비교하는 방법이 있다. 만약 이러한 방법으로 검색을 한다면

문자열의 길이만큼 비교횟수가 증가해서 시간 복잡도가 굉장히 커진다. ( O(N*M), N : 텍스트의 길이, M : 비교 문자열의 길이)

하지만 KMP 알고리즘을 사용하면 O(N+M)의 시간 복잡도로 이 문제를 해결할 수 있다!

KMP 알고리즘의 핵심은 이전에 비교했던 정보를 활용해 검색에 이용하는 것이다.

예를 들어 ABCDABCDABEE 가 있을때 ABCDABE 문자열을 찾아보자.

맨 앞에서 ABCDAB 까지 동일하지만 마지막 글자가 다르다. 이러한 경우에 이 정보를 가지고 다음 비교에 이용한다.

자세한 내용은 구현에서 다시 보자.

2. 구현

KMP 알고리즘을 이해하기 위해서는 접두사와 접미사를 알아야한다.

banana를 예로 들어보자.

1) banana의 접두사

b , ba , ban , bana, banan, banana

총 6개가 banana의 접두사이다

2) banana의 접미사

a, na, ana, nana, anana, banana

총 6개가 banana의 접미사이다.

다음으로 pi 배열에 대해 알아야한다.

pi[i]는 주어진 문자열의 0~i 까지의 부분 문자열 중에서 [접두사 == 접미사]가 될 수 있는 부분 문자열 중에서 가장 긴 것의 길이이다.

이 때 접두사가 0~i 까지의 부분 문자열과 같으면 안된다.

예시를 통해 알아보자.

문자열 QWQQWQW 의 pi를 구해보자.

[i]                        [부분 문자열]                        pi[i]

0                                Q                                    0

1                                QW                                  0

2                              QWQ                                 1              -> Q

3                             QWQQ                               1              -> Q

4                           QWQQW                             2              -> QW

5                          QWQQWQ                           3              -> QWQ

6                        QWQQWQW                          2              -> QW

** 이 이상은 설명하기가 어렵네요... [http://bowbowbow.tistory.com/6] 이분이 설명을 매우 잘해두셨으니 참고하시는게 훨씬 도움될것입니다! **

[문자열 검색 알고리즘 예제 : http://gyutts.tistory.com/96]