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

1. KMP알고리즘이란 

 

문자열 검색 알고리즘을 지난번 브루트 포스 알고리즘으로 하나하나 반복해서 검색하는 것을 알아보았었다.

M개의 문자열(text)에서, N문자열(pattern)이 어디에 포함되어 있는지를 검색하기 위해서, text를 돌면서 pattern과 일치하는 지를 하나하나 검색했었다. 따라서 시간복잡도는 O(MN)이였다.

이를 O(M+N)의 시간 복잡도로 줄일 수 있는 방법이 바로 KMP 알고리즘이다.

 

Knuth, Morris, Pratt 세 사람이 거의 같은 시기에 고안했기 때문에 이들의 이름 앞 글자를 각각 따서 KMP 법이라고 부른다.

그럼 KMP 알고리즘은 어떻게 문자열 검색을 하기에 시간복잡도를 O(N+M)으로 낮출 수 있을까

 

2. KMP알고리즘을 이해 하기에 앞서 알아야 하는것

(1) 접두사(Prefix)와 접미사(Suffix)의 이해

(2) pi 배열

pi[i]는 주어진 문자열의 0~i까지의 문자열 중에서 prefix와 suffix가 같은 문자열 중 가장 긴 것의 길이이다.

(prefix가 0~i까지의 부분 문자열과 동일하면 안됨.)

 

예를들어서, "ABAABAB" 문자열서 pi배열을 구해 본다면 다음과 같다.

p[0] = 0 (A)

p[1] = 0 (AB)

p[2] = 1 (ABA)

p[3] = 1 (ABAA)

p[4] = 2 (ABAAB)

p[5] = 3 (ABAABA)

p[6] = 2 (ABAABAB)

 

3. KMP 알고리즘의 원리

브루트 포스 알고리즘은, 일단 text와 pattern을 한 글자씩 비교한 후, 일치하면 계속 비교를 해 나가는 것이고,

일치 하지 않는다면 한칸 이동해서 비교를 해 나가는 단순한 방법이였다.하지만 이 과정에서 낭비되는 정보가 있는데, 예를들어 text에서 pattern이 'ABCABD'라는 것을 검색할때,한 글자씩 검색하는것은 동일한데, 문자열 'ABCABD'에서 text가 'ABCAB' 까지 일치했다면, 한칸 이동해서 비교를 하는 것이 아닌, suffix와 prefix가 동일한 AB부분으로 이동하여 그 부분부터 검색 하면 되는 것이다. 그래서 시간이 줄어드는 원리가 KMP 알고리즘의 원리이다.

 

 

위 에서 볼 수 있듯, text의 index는 절대 다시 뒤로 돌아가지 않는것이 KMP 알고리즘의 아이디어 이다.

text와 pattern의 일치하지 않는곳 까지 한 문자씩 비교를 했을때, 검사를 마친 문자열에서, pi[i]값이 0이라면, pattern의1번째 문자부터 일치하지 않는곳으로 뛰어넘어 다시 검사를 하고,

prefix와 suffix가 동일한 곳으로 넘어가 pattern의 prefix 이후 부터 비교 하는 방식이다.

즉, 일치했었다는 정보에 주목하여, 미리 전처리 해둔 pi 배열을 이용해 많은 중간 시도를 건너 뛸 수 있게 한다.

 

구현 방법은 다음과 같다. 

먼저 pattern에 대한 pi 배열 (suffix와 prefix가 같은 문자열 중 가장 긴 길이)을 만드는데 pattern의 길이가 N이라고 한다면, O(N)의 시간복잡도가 나오고, text의 index는 절대 뒤로 오지 않기 때문에 text의 길이가 M이라 했을때 한번 도는 시간 복잡도 O(M)이기에 KMP 알고리즘의 시간 복잡도는 O(M+N)이 된다.

 

(1) pattern에서 pi배열의 구현방법 :

인덱스인 j는 0으로, i = 1로 설정한다. j는 prefix에 대한 인덱스이고 i는 suffix에 대한 인덱스이다.

pi배열의 pi[0] = 0으로 설정하고, pi배열의 1번째에는, pattern의 j 문자와 i문자 비교 해서 (prefix, suffix 비교) 같지 않으면 0 을 입력하고 i를(suffix)를 1 증가 시킨다. 만약 j문자와 i문자가 같으면(suffix == prefix) j + 1 (index는 0부터 시작하므로 suffix index인 j까지 같다는 의미) 을 입력하고 i와 j를 둘다 증가시킨다.  

j문자와 i문자가 다르면, pi[j-1]의 값으로 index j를 이동해서 다시 비교 하고, j = 0이면 i를 증가시킨다. 이 부분이 jump의 부분인데, j와 i 문자가 다르면, j-1까지 중 prefix 다음부터 비교를 하는 것이다. preifx가 바로 pi[j-1]이므로 그 부분의 index로 부터 비교 하는 것이다. (아래 그림을 보면 왜 mismatch시 pi[j-1]의 index로 j가 이동하는지 알게 될 것이다.

(ㅇ출처 : https://velog.io/@dkswlgus00/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-13%EC%A3%BC%EC%B0%A8-1%EC%B0%A8%EC%8B%9C

(2) text와 pattern의 비교

마찬가지로, text의 index를 i, pattern의 index를 j라고 할때, i는 계속 앞으로만가지 감소시키지 않는다.

i와 j에 해당하는 문자를 비교해서 같으면 1씩 증가시켜서 다시 비교하고, 다르면 pi배열을 이용해 

pi[j-1]로 index를 이동해서 jump를 하여 다시 비교하는데, j가 0이 될때 까지 pi배열을 사용하고, j가 0이 되면 i를 1 증가시킨다. 이렇게 반복하여 pattern의 length만큼 일치하게 된다면, i - j 의 위치가 return 되면 되는 것이다.

 

즉 KMP 알고리즘의 핵심은, prefix와 suffix를 이용하여, pi 배열을 만든 다음, 그 pi 배열을 이용해 text와 pattern의 mismatch가 있을때 점프하여 prefix 다음 부터 비교 하게 되는 것이다.

 

Reference : 

Do it! 자료구조와 함께 배우는 알고리즘 입문 자바편 (이지스 퍼블리싱)

https://www.youtube.com/watch?v=GTJr8OvyEVQ 

https://www.youtube.com/watch?v=V5-7GzOfADQ 

https://velog.io/@dkswlgus00/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-13%EC%A3%BC%EC%B0%A8-1%EC%B0%A8%EC%8B% 

https://bowbowbow.tistory.com/6 

KMP : 문자열 검색 알고리즘

https://www.youtube.com/watch?v=GTJr8OvyEVQ

[알고리즘] 13주차 1차시

4. Java로 구현