KMP

커누스 모리스 프랫 알고리즘(KMP 알고리즘)은 문자열 검색 알고리즘으로, 불일치가 발생할 때 단어 자체가 다음 일치가 시작될 수 있는 위치를 결정할 수 있는 것을 활용하여 이전에 일치한 문자를 건너 뛰고 비교를 계속하는 알고리즘이다. 전체 문자열에 대해서 특정 단어를 찾는 연산을 $O(M + N)$에 수행할 수 있다.

이론

패턴을 이용하여 부분 일치 테이블 배열 (pi[])을 작성하고, 매칭이 실패했을 때 패턴 포인터가 돌아갈 곳을 계산한다. 즉 pi[]배열은 매칭 실패 시 해당 비교 문자열의 시작 인덱스를 가리키도록 하는 것이다 만약 비교 문자열 인덱스가 3에서 틀렸다고 가정하면 문자열 인덱스 2까지는 맞았다는 뜻이므로 pi[2]를 검사하여 해당 배열에 저장된 값으로 비교 문자열을 시작하는 것이다.

pi[]배열은 1번 인덱스부터 각 인덱스마다 처음과 해당 인덱스까지의 부분 문자열 중 접두사와 접미사가 일치하는 최대 길이를 계산하여 작성한다.

알고리즘 구현

KMP 알고리즘을 구현해보도록 하자. 주어진 다음 문자열이 존재할 때,

AAAVAAVDAA

여기서 AAVDAA라는 단어를 검색해보도록 하겠다.

접미사 테이블 생성

구하고자 하는 ‘AAVDAA’라는 문자열을 대상으로 KMP 알고리즘의 핵심이 되는 부분인 접두사-접미사 일치 테이블을 먼저 구해야 한다.

int[] getPi(String pattern) {
    int size = pattern.length();
    int[] pi = new int[size];

    // 접두사 인덱스
    int pos = 0;
    for (int i = 1; i < size; i++) {
    while (pos > 0 && pattern.charAt(i) != pattern.charAt(pos)) {
        pos = pi[pos - 1];
    }

    if (pattern.charAt(i) == pattern.charAt(pos)) {
        pi[i] = ++pos;
    }
    }
    return pi;
}

getPi("AAVDAA")를 수행한 결과는 다음과 같다.

인덱스 (i)	0	1	2	3	4	5
문자	A	A	V	D	A	A
LPS 값	0	1	0	0	1	2

이는 i + 1 만큼의 길이를 대상으로 접두사와 접미사가 일치하는 부분 문자열(패턴의 0번째부터 i번째까지)의 최대 길이를 표시하는 것이다. 단계별로 살펴보도록 하자. pi 배열을 기준으로 다음과 같은 과정의 연산이 이루어진다.

i = 1 (AA)
접두사 후보: A, AA
접미사 후보: A, AA
접두사와 접미사가 같으므로 pi[1] = 1

i = 2 (AAV)
접두사 후보: A, AA, AAV
접미사 후보: V, AV, AAV
공통된 것이 없으므로 pi[2] = 0

i = 3 (AAVD)
접두사 후보: A, AA, AAV, AAVD
접미사 후보: D, VD, AVD, AAVD, AAVD
공통된 것이 없으므로 pi[3] = 0

i = 4 (AAVDA)
접두사 후보: A, AA, AAV, AAVD, AAVDA
접미사 후보: A, DA, VDA, AVDA, AAVDA
접두사와 접미사가 같은 부분이 하나가 있으므로 pi[4] = 1

i = 5 (AAVDAA)
접두사 후보: A, AA, AAV, AAVD, AAVDA, AAVDAA
접미사 후보: A, AA, DAA, VDAA, AVDAA, AAVDAA
AA로 2 길이 만큼의 일치가 존재하므로 pi[5] = 2

이를 활용하여 검사 중에 불일치가 발생했을 경우 중복 검사를 피하고 불일치가 발생한 부분이 가리키는 접미사 인덱스로 이동하여 마저 검사를 수행할 수 있다. 어떻게 중복 검사를 피할 수 있을까? 이는 패턴 검색 로직을 통해 알아보도록 하자.

패턴 검색

void kmp(String org, String ptn) {
    int[] pi = getPi(ptn);

    // 비교문자를 위한 인덱스
    int pos = 0;
    int patternLength = ptn.length() - 1;
    int len = org.length();

    // 원문을 위한 반복문과 인덱스 i
    for (int i = 0; i < len; i++) {
        while (pos > 0 && org.charAt(i) != ptn.charAt(pos)) {
            pos = pi[pos - 1];
        }

        if (org.charAt(i) == ptn.charAt(pos)) {
            // 원문에서 패턴과 일치하는 문자열을 찾은 경우
            if (pos == patternLength) {
                System.out.println(i - patternLength + " 에서 발견됨");
                // 다음 패턴을 찾기 위한 코드
                // pi에 모든 비교 문자열의 일치 개수가 있으므로
                // pos = 0이 아닌 다음 코드가 들어있어야 함
                pos = pi[pos];
            } else {
                pos++;
            }
        }
    }
}

pos는 검색하려는 문자열의 인덱스이고, i 값은 원본 문자열의 처음부터 끝까지 진행된다. 원본 문자열은 AAAVAAVDAA이고, 검색 문자열은 AAVDAA일 때를 가정해보도록 하자.

i = 0, pos = 0
ptn.charAt(pos) = A, org.charAt(i) = A, pos < patternSize - 1 then pos++

i = 1, pos = 1
ptn.charAt(pos) = A, org.charAt(i) = A, pos < patternSize - 1 then pos++, pos = 2

i = 2, pos = 2
ptn.charAt(pos) = V, org.charAt(i) = A, then pos = pi[1], pos = 1

i = 3, pos = 1
ptn.charAt(pos) = A, org.charAt(i) = V, then pos = pi[0], pos = 0

i = 4, pos = 0
ptn.charAt(pos) = A, org.charAt(i) = A, pos < patternSize - 1 then pos++

i가 2일 때를 살펴보자. 두 비교 문자가 다르기 때문에 pi 배열을 활용하여 비교를 시작할 위치를 지정해주는 것이다. 즉, pi 배열은 문자가 틀렸을 경우 다시 비교를 시작할 인덱스 값을 담아두는 배열인 것이다.

참고 자료

[문자열 탐색] KMP(Knuth-Morris-Pratt) 알고리즘

KMP : 문자열 검색 알고리즘