[알고리즘] KMP 알고리즘 (Knuth–Morris–Pratt Algorithm)

KMP 알고리즘

KMP 알고리즘은 문자열 중에 특정한 패턴을 찾아내는 문자열 검색 알고리즘이다.

 

보통 문자열을 검색하기 위해 자바에서는 아래와 같이 indexOf를 이용해서 쉽게 문자열 포함 여부 및 포함 위치를 알아낼 수 있다.

 

String str1 = "abcdefgh";
String str2 = "cdef";

System.out.println(str1.indexOf(str2)); // 2

 

하지만 이 방법은 모든 경우를 비교해서 찾아내는 방법으로 최악의 시간 복잡도를 가진다.

 

그래서 짧은 문자열이나 반복 작업이 아니라면 indexOf를 사용하는 것이 괜찮을지라도 긴 문자열이나 문자열 검색을 자주 실행해야 한다면 더 효율적인 문자열 검색 알고리즘이 필요할 것이다.

 

본인도 백준 문제(16916 - 부분 문자열)를 풀다가 효율적인 문자열 검색이 필요해서 현재 KMP 알고리즘을 공부하고 정리 후 다시 문제를 를 풀어보려고 한다.

 

그러면 본격적으로 KMP 알고리즘이 어떻게 문자열 검색을 효율적으로 하는지 알아보자.

 

KMP 알고리즘은 접두사와 접미사를 이용하여 반복되는 연산을 최대한 줄이는 방법이다. 이때 문자열 검색 시 불필요한 문자 간 비교를 없애기 위해 실패 함수라는 것을 사용한다.

 

쉽게 말하면 일치했던 부분까지는 남겨두고 그 뒤부터 검사를 하는 방식인 것이다.

 

KMP 알고리즘을 자바로 작성하면 아래와 같다.

 

// 실패함수 찾기
public static int[] findPi(String P) {
    int[] result = new int[P.length()]; // KMP 알고리즘 실행 중 일치하지 않는 문자가 있을 때 어디서부터 검색을 해야할지 알려주는 배열
    int begin = 0;
    for (int i = 1; i < P.length(); i++) {
        while (begin > 0 && P.charAt(i) != P.charAt(begin)) {
            begin = result[begin - 1];
        }
        if (P.charAt(i) == P.charAt(begin)) {
            result[i] = ++begin;
        }
    }
    return result;
}

public static int KMP(String S, String P) {
    int[] pi = findPi(P); // pi 배열
    int begin = 0;
    for (int i = 0; i < S.length(); i++) {
        while (begin > 0 && S.charAt(i) != P.charAt(begin)) {
            begin = pi[begin - 1];
        }
        if (S.charAt(i) == P.charAt(begin)) {
            if (begin == P.length() - 1) {
                return i - P.length() + 2;
            } else {
                begin++;
            }
        }
    }

    return -1;
}

 

처음 보면 많이 헷갈리기 때문에 머릿속으로 계속 몇 번 생각해봐야지 눈 감고도 코드를 작성할 수 있을 것 같다.