오늘은 문자열 검색 알고리즘 중에 KMP법에 대해 알아보자.

📘 KMP법

KMP법은 다른 문자를 만나면 패턴을 1칸씩 옮긴 다음 다시 패턴의 처음부터 검사하는 브루트-포스법과는 다르게 중간 검사 결과를 효율적으로 사용하는 알고리즘이다.

📜 KMP법 원리

그림으로 예시를 보자.

다음 텍스트 "ZABCABXACCADEF"에서 패턴 "ABCABD"를 검색하는 경우를 예로 들어보자.
다음 그림과 같이 텍스트, 패턴의 1번째 문자부터 순서대로 검사한다.
텍스트의 1번째 문자 'Z'는 패턴에 없는 문자이므로 일치하지 않는다고 판단한다.

---

일치하지 않으므로 패턴을 1칸 뒤로 이동시킨다.
이때 패턴을 처음부터 순서대로 검사하면 다 동일하지만 마지막 문자가 'D' 여서 텍스트의 X와 일치하지 않는다.
여기서 텍스트의 "AB"와 패턴의 "AB"가 일치한다는 점을 이용하면 된다.
이 부분은 '이미 검사를 마친 부분' 이므로 텍스트의 'X' 다음 문자부터 패턴의 "CABD"가 일치하는지만 검사하면 된다.

---

다음 그림과 같이 "AB"와 'X'를 한 번에 3칸 이동시키고 3번째 문자인 'C'부터 검사하면 된다.

---

이와 같이 KMP법은 텍스트와 패턴의 겹치는 부분을 찾아내어 검사를 다시 시작할 위치를 구한다.
이런 방법을 패턴을 최소의 횟수로 옮겨 알고리즘의 효율을 높인다.

하지만 몇 번째 문자부터 다시 검색을 시작할지 패턴을 이동시킬 때마다 다시 게산해야 한다면 높은 효율을 기대할 순 없다. 그래서 '몇 번째 문자부터 다시 검색할지'에 대한 값을 미리 '표'로 만들어 이러한 문제를 해결한다.

✏ KMP 표만들기

표를 작성할 때는 패턴 안에서 중복되는 문자의 나열을 먼저 찾아야 한다.
이 과정에서 KMP법을 사용한다. 패턴 안에서 중복되는 문자의 나열을 찾기 위해 패턴끼리 겹쳐놓고 생각해보자.
패턴의 1번째 문자가 서로 다른 경우 아래의 패턴을 1칸 뒤로 옮기고 1번째 문자부터 다시 검사한다.

패턴 "ABCABD"를 1칸 뒤로 옮긴 다음 겹친다.
그림을 보면 붉은 부분이 겹치지 않으므로 패턴을 옮긴 다음 앞쪽의 1번째 문자부터 검사를 다시 시작해야 한다는 것을 알 수 있다. 따라서 표에서 2번째 문자(B)의 값을 0으로 한다.
표에서 2번째 값이 0인 이유는 아래에 위치시킨 패턴의 첫 번째 문자의 인덱스가 0이고 이 위치에서 다시 검사를 시작하기 때문이다.

---

패턴을 다시 1칸 뒤로 옮긴다. 문자가 일치하지 않으므로 표에서 3번째 문자(C)의 값을 0으로 한다.

---

패턴을 1칸 뒤로 옮기면 "AB"가 일치한다. 여기서 알 수 있는 사실은 다음과 같다.

1. 패턴의 4번째 문자 'A'까지 일치한다면 아래에 위치한 패턴을 1칸 옮긴 다음 'A'를 건너뛰고 
2번째 문자부터 검사할 수 있다.

2. 패턴의 5번째 문자 'B'까지 일치한다면 아래에 위치한 패턴을 1칸 옮긴 다음 "AB"를 건너뛰고
3번째 문자부터 검사할 수 있다.

따라서 표에서 두 문자의 다시 시작하는 값을 1, 2로 하고 이어서 2칸 뒤로 옮기면 문자가 일치하지 않으므로 마지막 문자의 'D'값을 0으로 하면 다음과 같은 표가 완성된다.

📜 KMP법 코드

이제 메서드를 통해 알아보자.

 // KMP법에 의한 문자열 검색
    static int kmpMatch(String text, String pattern) {
        int pt = 1;     // text 커서
        int pp = 0;     // pattern 커서
        int[] skip = new int[pattern.length() + 1];  // 건너뛰기 표

        // 건너뛰기 표 만들기
        skip[pt] = 0;
        while (pt != pattern.length()) {
            if (pattern.charAt(pt) == pattern.charAt(pp))
                skip[++pt] = ++pp;
            else if (pp == 0)
                skip[++pt] = pp;
            else
                pp = skip[pp];
        }

        // 검색
        pt = pp = 0;
        while (pt != text.length() && pp != pattern.length()) {
            if (text.charAt(pt) == pattern.charAt(pp)) {
                pt++;
                pp++;
            } else if (pp == 0)
                pt++;
            else
                pp = skip[pp];
        }
        
        if (pp == pattern.length())
            return pt - pp;     // pt - pp를 반환
        return -1;              // 검색 실패
    }

표만들기 주석부분에서 다시 시작 값의 표를 만들고 검색 주석부분에서 검색을 수행한다.
KMP법에서 텍스트를 스캔하는 커서 pt는 다시 뒤로 돌아오지 않는다.
하지만 KMP법은 브루트-포스법보다는 복잡하고, Boyer-Moore법과는 성능이 같거나 좋지 않아 실제 프로그램에서는 거의 사용하지 않는다.