KMP법
KMP법이란? 부르트-포스법의 단점인 이미 검사한 부분을 또 검사해야되는 단점을 보완하여 그때까지 검사한 결과를 효과적으로 이용하는 알고리즘이다.
KMP법의 시간 복잡도
KMP법의 시간 복잡도는 최악의 경우에 O(n)으로 매우 빠르다.
반면 처리하기가 복잡하다는점, 패턴 안에 반복하는 요소가 없으면 효율이 떨어진다는 단점이 존재한다.
KMP법 알아보기
브루트-포스법은 일치하지 않는 문자를 만난 단계에서 그때까지 검사한 결과를 버리고 패턴을 텍스트의 다음 칸으로 옮긴 다음 패턴의 첫 번째 문자부터 다시 검사하는데, KMP법은 앞서 검사한 결과를 버리지 않고 이를 효과적으로 이용한다.
※ Knuth, Morris, Pratt이 거의 같은 시기에 고안했기에 이들의 이니셜을 따 KMP.
텍스트 "ZABCABXACCADEF"에서 패턴 "ABCABD"를 검색해보자.
A. 텍스트와 패턴의 1번째 문자부터 순서대로 검사한다. 텍스트의 1번 문자가 Z이므로 바로 일치하지 않는다고 판단한다.
│Z│A│B│C│A│B│X│A│C│C│A│D│E│F│
X
│A│B│C│A│B│D│B. 이제 패턴을 1칸 뒤로 옮긴다. 이때 패턴의 처음부터 순서대로 검사하면 패턴의 마지막 문자 'D'가 텍스트의 'X'와 일치하지 않는다.
│ Z │ A │ B │ C │ A │ B │ X │ A │ C │ C │ A │ D │ E │ F │
O O O ◎ ◎ X
│ A │ B │ C │ A │ B │ D │C. 여기서 ◎표시 된 부분의 텍스트 A,B가 패턴의 A,B와 일치하고 있는 것에 주목하자. '이미 검사를 마친 부분'으로 보면, 텍스트의 'X'다음 문자부터 패턴의 "CABD"가 일치하는지만 검사하면 된다. 그래서 패턴을 다음과 같이 "AB"가 겹치도록 한 번에(3칸) 이동 시키고, 3번째 문자인 'C'부터 검사하면 된다.
│ Z │ A │ B │ C │ A │ B │ X │ A │ C │ C │ A │ D │ E │ F │
◎ ◎ ↑여기부터 검사
│ A │ B │ C │ A │ B │ D │일단 이를 위해서는 패턴 안에서 중복되는 문자열을 찾아야 한다.
이때 표를하나 작성하는데, 몇 번째 문자부터 다시 검색을 시작할지에 대한 값을 표로 작성해야 한다.
이때도 KMP법의 아이디어를 이용하는데, 패턴 안에서 중복되는 문자열을 찾기 위해 패턴끼리 겹쳐놓고 생각해보자. 텍스트와 패턴의 1번째 문자가 서로 다를 경우 패턴을 1칸 뒤로 옮기고 패턴의 1번째 문자부터 다시 검사해야 하는 것은 분명하므로 패턴의 2번째 문자부터 생각한다.
패턴의 2번째 문자'B'부터 검사한 결과 패턴은 겹치는게 없으므로
문자(B)의 다시 시작하는 값은 0이된다.
│ A │ B │ C │ A │ B │ D │
l 안겹침
│ A │ B │ C │ A │ B │ D │
다시 패턴을 1칸 뒤로 옮긴다. 문자가 또 일치하지 않기에 3번째 문자C의 값을 0으로 설정한다.
│ A │ B │ C │ A │ B │ D │
l 안겹침
│ A │ B │ C │ A │ B │ D │
다시 패턴을 1칸 뒤로 옮겨서 검사해보면 "AB"가 연속으로 일치하는것을 볼 수 있다. 여기서 다음과 같은 사실을 알 수 있다.
- 패턴의 4번째 문자 'A'까지 일치하면 패턴을 텍스트의 다음 'A'까지 한번에 옮긴 뒤 'A'를 건너뛰고 2번째 문자부터 검사할 수 있다.
- 패턴의 4번째, 5번째 문자 'AB'까지 일치하면 패턴을 텍스트의 다음 'AB'까지 한번에 옮긴 뒤 'AB'를 건너뛰고 3번째 문자부터 검사할 수 있다
│ A │ B │ C │ A │ B │ D │
l l 겹치게 됨!
│ A │ B │ C │ A │ B │ D │따라서 표에서 4번째와 5번째 문자의 경우 다시 시작하는 값을 1,2로 한다.
한칸 더 옮겨서 D를 기준으로 검사해보면 겹치는게 사라지기에 D는 0이된다.
이렇게 완성된 표를 활용해서 KMP법을 사용해 문자열을 검색하는 프로그램을 만들 수 있다.
KMP법 예제코드
public class KMP {
static int kmpMatch(String txt, String pat) {
int pt = 1;
int pp = 0;
int[] skip = new int[pat.length() + 1]; // 건너뛰기 표를 위한 배열
// 건너뛰기 표 만드는 과정
skip[pt] = 0;
while (pt != pat.length()) {
if (pat.charAt(pt) == pat.charAt(pp))
skip[++pt] = ++pp;
else if (pp == 0)
skip[++pt] = pp;
else pp = skip[pp];
}
// 검색 과정
pt = pp = 0;
while (pt != txt.length() && pp != pat.length()) {
if (txt.charAt(pt) == pat.charAt(pp)) {
pt++;
pp++;
} else if (pp == 0)
pt++;
else
pp = skip[pp];
}
if (pp == pat.length()) // 패턴의 모든 문자를 대조
return pt = pp;
return -1; // 검색 실패를 의미하는 -1 반환
}
}kmpMatch 메서드가 전달받은 인스나 반환값은 브루트-포스법의 함수 bfMatch와 같다.
처음 while에서 건너뛰기 표를 만든 후, 다음 while문에서 검색을 수행한다. KMP법에서 텍스트를 스캔하는 커서 pt는 앞으로 나아갈 뿐 뒤로 돌아오는 일은 없다.
제일 중요한 점
KMP법은 브루트-포스법보다 성능이 좋긴하나, 복잡하다. 심지어는 다음 포스트에 배울 보이어&무어법에 비하면 성능이 같거나(최악의경우는 같음) 낮아(평균적으로는 낮음) 실제 프로그래밍에서는 거의 사용하지 않는 방법이다.
