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

 이번에 다루게 될 알고리즘은 KMP 알고리즘으로 대표적인 문자열 매칭 알고리즘입니다. KMP 알고리즘은 접두사와 접미사의 개념을 활용하여 문자열을 점프하는 기법입니다. 접두사는 앞에 있는 문자열, 접미사는 뒤에 있는 문자열로 abacaaba가 있을 때 다음과 같습니다.

 

접두사    접미사
 a b a c a a b c

 우리가 구해야 할 것은 위와 같은 접두사와 접미사가 일치하는 최대 길이입니다.

 

길이	문자열	최대 일치 길이
1	a	0
2	ab	0
3	aba	1
4	abac	0
5	abaca	1
6	abacaa	1
7	abacaab	2
8	abacaaba	3

 

 위의 표처럼 접두사와 접미사가 일치하는 경우를 구하게 되면 KMP 알고리즘의 기반이 됩니다. 이제 위와 같은 접두사와 접미사의 최대 일치 길이를 어떻게 구하는지 알아보겠습니다.

 

접두사와 접미사의 최대 일치 길이

접두사의 위치를 j, 접미사의 위치를 i라고 한다면, 기본적인 동작과정은 j와 i가 일치하는 경우, j와 i가 일치하지 않는 경우에 따라 나뉘게 됩니다.

 

1. j와 i위치의 문자가 일치한 경우

 해당 위치에서 접두사와 접미사가 일치하다는 의미입니다. 이제 다음 위치를 탐색해야하므로 j와 i의 위치를 오른쪽으로 한 칸씩 이동해줍니다.

 

2. j와 i위치의 문자가 일치하지 않는 경우

 접두사와 접미사가 불일치하다는 의미입니다. 다시 검사를 해야하지만, 완전 처음부터 검사하는 것은 비효율적입니다. 그래서 여태까지 일치했던 곳에서부터 재탐색합니다. 즉, 접두사와 접미사의 일치 여부가 담긴 table을 참고하여 j의 위치를 table[j-1]에서 가리키는 위치로 이동시켜줍니다. (j-1)인 이유는 최소 j-1위치까지는 접두사와 접미사가 일치하다는 의미로 j의 이동을 최소화할 수 있습니다.

 

Table 생성과정

과정 1

과정2

과정3

 

이제 위의 과정들을 Java코드로 확인해보겠습니다.

 

import java.util.*;
import java.io.*;

public class KMP {
    public static void main(String[] args) throws IOException {
        String str = "ababaca";
        int[] table = makePatternTable(str);
        System.out.println(Arrays.toString(table));
    }

    public static int[] makePatternTable(String str) {
        int strSize = str.length();
        int j = 0;
        int[] table = new int[strSize];
        
        for(int i=1; i<strSize; i++) {
            while(j > 0 && str.charAt(j) != str.charAt(i)) {
                j = table[j-1];
            }
            
            if(str.charAt(j) == str.charAt(i)) {
                table[i] = j+1;
                j += 1;
            }
        }

        return table;
    }
}

 위와 같이 접두사와 접미사를 하나씩 늘려가며 비교하다가 일치하지 않는 경우가 발생하면 지금까지 일치했던 부분으로 되돌아가서 다시 검사하는 방식을 구현할 수 있습니다. 이를 통해 '최대 일치 길이' 테이블을 구축할 수 있습니다.

 

이제 예를 통해 두 문자열을 비교하는 방법을 확인하겠습니다.

 

Parent -> abababacabaababacaca
Pattern -> ababaca
최대 일치 길이 -> table 배열

 

문자열 매칭 동작과정

과정1

과정2

과정3

과정4

과정5

 

 이제 위의 과정들을 실제 Java 코드로 구현해보겠습니다.

 

import java.util.*;
import java.io.*;

public class KMP {
    public static void main(String[] args) throws IOException {
        String parent = "abababacabaababacaca";
        String pattern = "ababaca";
        startKMP(parent, pattern);
    }

    public static int[] makePatternTable(String str) {
        int strSize = str.length();
        int j = 0;
        int[] table = new int[strSize];
        
        for(int i=1; i<strSize; i++) {
            while(j > 0 && str.charAt(j) != str.charAt(i)) {
                j = table[j-1];
            }
            
            if(str.charAt(j) == str.charAt(i)) {
                table[i] = j+1;
                j += 1;
            }
        }

        return table;
    }

    public static void startKMP(String parent, String pattern) {
        System.out.println(parent);
        System.out.println(pattern);

        int[] table = makePatternTable(pattern);
        System.out.println(Arrays.toString(table) + "\n");

        int parentSize = parent.length();   
        int patternSize = pattern.length();
        int j = 0;

        for(int i=0; i<parentSize; i++) {
            while(j>0 && parent.charAt(i) != pattern.charAt(j)) {
                j = table[j-1];
            }

            if(parent.charAt(i) == pattern.charAt(j)) {
                if(j == patternSize - 1) {
                    System.out.println((i-patternSize+1) + "번째 index에서 동일한 문자열 발견");
                    j = table[j];
                } else {
                    j += 1;
                }
            }
        }
    }
}

 

 최근 포스팅에서는 Naive 알고리즘과 Hashing 기법, 라빈 카프 알고리즘에 대해 배웠습니다. 이번 포스팅에서는 접두사와 접미사를 활용한 KMP 알고리즘을 공부하며, 어떻게 하면 문자열 매칭 알고리즘의 효율성을 높일 수 있는지 알 수 있었습니다.

 KMP 알고리즘은 접두사와 접미사를 통해 문자열 탐색에 사용하는 인덱스를 점프하는 것이 포인트입니다. 그리고 이러한 원리를 이해하는 것이 코드를 구현하는 것보다 우선적으로 해야합니다.

 

 

 

 

 

 

(출처: https://devje8.tistory.com/24)