[코딩 알고리즘] KMP 알고리즘

이번 포스팅에서는 문자열 매칭 알고리즘의 대명사 KMP((Knuth–Morris–Pratt Algorithm) 알고리즘에 대해서 알아보겠다.

커누스-모리스-프랫 이 세 사람이 고안해낸 알고리즘이고 보통은 이름의 앞글자만 따서 KMP라고 줄여서 부른다. KMP 알고리즘은 주어진 보통 웹 브라우저 크롬, IE, 파이어폭스 등에서 원하는 글자를 찾는 기능 (ctrl+f)을 사용할 때 우리도 모르게 사용하고 있다. 조금 포멀 하게 말하자면 찾고 하자는 단어 "W"가 주어진 평문 "S"에서 몇 번 발견되는지 검색을 하는 알고리즘이다.

 

 

이 알고리즘은 The art of Computer Programming의 저자로 명성이 높은 커누스의 오토마타 이론에서부터 독자적으로 발전하였다. 모리스는 첫 번째 원리를 오토마타에서부터 영감을 얻었고 최초 선형 시간(linear time complexity aka O(N) 내에 문자열 매칭 시물레이션을 전문화하는 데 성공하였다 프랫은 초기버전 알고리즘의 효율성 향상에 기여했다. 

KMP 알고리즘 원리

다시 문자열 매칭 문제로 돌아와서 생각해보자. S라는 문자열안에서 W라는 문자열이 존재하는지를 찾아야 한다. 예를 들자면 "Hello World!"안에 "World"가 어느 위치에 몇 번 존재하는지 알아맞추는 알고리즘이다. 

 

언제나 그렇듯 가장 쉬운 접근 방법으로 생각해보자면 S 시작부터 끝까지 W의 문자열 길이만큼 반복해서 일일이 확인해보면 된다. 이 경우에 시간 복잡도는 O(N*M) - N은 S의 길이 M은 W의 길이 -이다.

 

앞서 말했듯 KMP는 위 시간 복잡도를 O(N) 선형 시간으로 줄이는 획기적인 알고리즘이다. (사실 자세히 하자면 O(N+M)이다. 하지만 N의 길이가 더 길다는 가정이므로 Big-O 표기법으로는 O(N)으로 해도 무방하다). 어떤 방법으로 선형 시간 안에 풀 수 있었을지 알아보도록 하자.

 

가장 기본이 되는 아이디어는 이미 찾은 것은 다시 반복하지 말자는 것이 기본이다. O(N*M) 알고리즘은 우리기 이미 알았던 정보는 무시하고 매번 새롭게 찾기 때문에 비효율이 발생하는 것이다. 

예제 : "abababc"에서 "ababc"가 있는지 찾아보자.

1. 두 문자열 첫 4글자가 "abab"가 똑같다.  5번째부터 틀리다.
2. 그리고 "abab"에서 "ab"가 반복이 된다.
3. 2번에 의해 "abababc"를 3번째부터 "ababc"를 찾아보도록 한다.
4. 3번째부터 찾아보니 "ababc"가 존재한다.

위 예제에서 알아볼 수 있는 KMP 알고리즘의 중요 핵심 2가지를 찾을 수 있다.

1. 첫 시도 시 매칭 하지 않는다고 다음 문자열로 가지 않는다. 가능한 중복되는 문자를 건너뛴다.
2. 일부 매칭 된 문자 열중 접두사(prefix)와 접미사(sufix)가 반복된다면 반복된 횟수만큼 스킵한다.

1번을 하기 위해서 알아야 하는 것이 2번이고 일반적으로 2번을 계산하는 것을 실패 함수(failure fucntion)라고 부른다.

 

실패 함수 (failure function)

실패 함수는 일부만 매칭 되었을 때 그중 접두사와 접미사가 얼마나 반복되는지 기록하여 몇 번만큼 건너뛸 수 있는지를 알려주는 역할을 한다. 일반적으로는 배열에 저장한다.

index	W의 일부 문자열	배열에 저장되는 값
0	a	0
1	ab	0
2	aba	1
3	abab	2
4	ababc	0

위 테이블에서 빨간색으로 표시한 것이 반복되는 접두사와 접미사이다. 위 예제에서는 3번째 인덱스까지 매칭이 되므로 배열에 저장돼있는 값 2 만큼 건너뛰고 진행하면 된다는 것을 알 수 있다. 

 

KMP Code 

이제 실패 함수를 코딩해보도록 하자.

private int[] failureFunction(String str){
        int n = str.length();
        int j = 0;
        int[] arr = new int[n];
        for(int i = 1; i < n; i++){
            while(j > 0 && str.charAt(j) != str.charAt(i)) j = arr[j - 1];
            if(str.charAt(j) == str.charAt(i)) arr[i] = ++j;

        }
        return arr;
    }

 

위와 같이 실패 함수를 만들 수 있다. 이제 이 실패 함수를 사용해서 KMP 알고리즘을 완성시켜보자.

 

public void matchString(String s, String w){
        int[] failrue = failureFunction(w); //실패함수 결과 배열
        
        int n  = s.length(), j = 0;
        for(int i = 0; i < n; i++){
            while(j > 0 && s.charAt(i) != w.charAt(j)) j = failrue[j - 1];	//불일치하면 몇번 건너뛸지 값을 받아옴
            if(s.charAt(i) == w.charAt(j)) j++;

            if(j == w.length()) {	//찾았으면 찾은 위치 프린트하고 더 존재하는제 계속 진행
                System.out.println(String.format("found matching string from %s to %s" , (i + 1 - w.length()),(i)));
                j = failrue[j - 1];
            }
        }
    }

 

KMP 알고리즘을 알고 있으면 스트링 문자열 문제에 대한 자신감이 많이 오를 것이라 생각한다. 문제에 따라서 실패 함수만을 사용하면 되는 경우도 있으니 꼭 잘 이해하도록 하자.