[알고리즘] 문자열 알고리즘 - KMP알고리즘

KMP 알고리즘

KMP 알고리즘이란?

KMP알고리즘은 문자열 알고리즘 중의 하나이다.

문자열 S에서 패턴P를 찾아야 할 때 사용한다.

예를 들어 

S = "ABAABABAABC"

P = "ABAABC" 일 때

 

일반적인 탐색

일반적인 탐색을 통해 찾게 된다면

아래와 같은 탐색과정을 거치게 된다.

S[5]부터 P를 찾을 수 있다.

 

시간 복잡도는 O(N*M)이다. (N: 문자열의 길이, M: 패턴의 길이)

 

KMP 알고리즘 활용

KMP알고리즘을 이용하여 조금 더 효율적으로 구해보자.

 

우선 KMP알고리즘을 이해하려면 접두사(prefix)와 접미사(suffix)의 개념을 이해해야한다.

ABCDE라는 문자열이 있을 때

접두사는 앞에서부터

A

AB

ABC

ABCD

ABCDE 가 된다.

접미사는 뒤에서부터

E

DE

CDE

BCDE

ABCDE 가 된다.

 

다음으로 pi배열을 선언한다.pi[i]는 원본 문자열의 모든 부분문자열을 순회하면서 

접두사와 접미사가 가장 길게 일치하는 수이다.

예를 들면 

문자열 S가 ABAABC라고 했을 때 pi는 다음과 같다.

이제는 KMP알고리즘을 사용할 준비가 됐다.

일반적 탐색과정을 다시 한 번 보자.

여기서 틀리지 않은 부분문자열은 ABAAB이고 pi[4]는 2이다.

따라서 다음 탐색은 S문자열의 1번인덱스부터 탐색하는 것이 아닌

인덱스 3번에서부터 다시 탐색하면 된다.

여기서도 마찬가지로 그다음 4번인덱스부터 시작하는 것이아니라

5번 인덱스부터 시작하면된다.

전부 일치하면 종료한다.

 

이 방법을 사용하면 시간복잡도를 최악O(N+M)으로 찾아낼 수 있다.

 

구현

public class KMP {
    public static void main(String[] args) {
        String S = "ABAABABAABC";
        String P = "ABAABC";
        int[] pi = setPi(P);

        System.out.println(search(S, P, pi));
    }

    static int[] setPi(String P) {
        int pLen = P.length();
        int[] pi = new int[pLen];

        int idx = 0;
        for (int i = 1; i < pLen; i++) {
            // idx가 0보다 크고 char가 일치하지 않는 경우
            while (idx > 0 && P.charAt(i) != P.charAt(idx)) {
                idx = pi[idx - 1];
            }

            // char가 일치하는 경우
            if (P.charAt(i) == P.charAt(idx)) {
                idx++;
                pi[i] = idx;
            }
        }
        return pi;
    }
    static int search(String S, String P,int[] pi) {
        int sLen = S.length();
        int pLen = P.length();

        int idx = 0;
        for(int i = 0; i < sLen; i++) {
            // S를 전부 순회하면서 다른 부분이 나오면 다음 순회인덱스를 바꿔줌
            while(idx > 0 && S.charAt(i) != P.charAt(idx)) {
                idx = pi[idx - 1];
            }

            if(S.charAt(i) == P.charAt(idx)) {
                // 끝까지 일치한 경우
                if(idx == pLen - 1) {
                    idx = pi[idx];
                    return 1;
                }
                else {
                    idx++;
                }
            }
        }
        return 0;
    }
}

 

 

[ 알고리즘과 문법을 공부한 내용을 정리해보는 공간입니다. 부족한 부분이나 잘못된 부분 지적해주시면 감사하겠습니다.]