문자열 KMP 알고리즘

1. 단순 문자열 비교 알고리즘

parent	a	e	a	b	a	c
pattern	a	b	a	c

e와 b가 다르므로 pattern을 한 칸 이동시켜 다시 확인합니다.

parent	a	e	a	b	a	c
pattern		a	b	a	c

e와 a가 다르므로 pattern을 다시 한칸 이동시킵니다.

parent	a	e	a	b	a	c
pattern			a	b	a	c

이런 식으로 한칸씩 이동시키며 문자열을 확인하면 O(N*M)의 시간 복잡도를 갖게 되어 비효율적입니다.

 

2. KMP 알고리즘

위의 알고리즘은 최악의 경우 오랜 시간이 걸릴 수 있으므로 모든 경우를 다 비교하지 않아도 부분 문자열을 찾을 수 있는 알고리즘인 KMP 알고리즘을 사용해야 합니다.

KMP 알고리즘은 접두사와 접미사를 활용하여 문자열을 점프하여 효율적으로 부분 문자열을 찾는 알고리즘 입니다.

 

ⓛ 접두사와 접미사가 일치하는 최대 길이 테이블 구하기

KMP 알고리즘을 수행하기에 앞서 먼저 접두사와 접미사가 일치하는 최대 길이를 구해야 합니다.

예를 들어 ABCAB의 경우 AB가 앞 뒤로 중복되므로 접두사와 접미사가 일치하는 최대 길이는 2입니다.

1. A -> 0
2. AB -> 0
3. ABC -> 0
4. A BC A -> 1
5. AB C AB -> 2
6. ABCABD -> 0
7. A BCABD A -> 1
8. AB CABD AB -> 2

static void makeTable(String pattern) {
    int idx = 0;
    for (int i = 1; i < pattern.length(); i++) {
        while (idx > 0 && pattern.charAt(idx) != pattern.charAt(i)) {
            idx = pi[idx-1];
        }
        if (pattern.charAt(idx) == pattern.charAt(i)) {
            idx++;
            pi[i] = idx;
        }
    }
}

다음과 같이 pattern의 idx와 i번째 인덱스 값이 같다면 idx와 i를 함께 증가시킵니다.

만약 다른 값을 가진다면 idx를 앞으로 이동시켜야 합니다.

 

이때 idx 값을 pi[idx-1]로 설정해주는 이유는

예를들어 ABACABAB가 있다고 했을 때 idx가 3을 가리키고 i가 7을 가리키고 있습니다.

이때 pattern.charAt(idx) != pattern.charAt(i) 이므로 idx를 앞으로 옮겨야 합니다.

이때 pi[idx-1] 값은 1입니다. 즉 C 앞의 ABA에서 ABA 가 중복된다는 뜻입니다. 이것은 ABACABA 에서ABA C ABA 굵은 글씨로 표현된 A가 모두 공통이라는 것을 의미합니다. 

이 말은 ABA C ABAB 굵은 글씨가 같은 값을 갖는다는 말이고, 이에 따라  ABACABAB 를 비교하면 된다는 의미입니다.

 

② 부분 문자열 찾기

parent	a	b	a	b	a	b	a	c
pattern	a	b	a	b	a	c	a

i는 parent에서 이동시키고, j는 pattern에서 이동시킵니다.

만약 parent.charAt(i) == pattern.charAt(j) 이면 i와 j를 함께 한 칸 이동시킵니다.

만약 위와 같이 다른 문자가 나타나면 pi[j-1] 값을 확인하여 j를 pi[j-1] 위치로 이동시킵니다.

static void kmp(String pattern, String parent) {
    int j = 0;
    for (int i = 0; i < parent.length(); i++) {
        while (j > 0 && pattern.charAt(j) != parent.charAt(i)) {
            j = pi[j-1];
        }
        if (pattern.charAt(j) == parent.charAt(i)) {
            if (j == pattern.length()-1) {
                System.out.println(i-pattern.length()+2+"번째에서 찾았습니다");
                break;
            }
            else
                j++;
        }
    }
}

 

 

전체 코드

public class Main {
    static int[] pi;
    public static void main(String[] args) {
        String pattern = "abacaaba";
        String parent = "ababacabacaabacaaba";
        pi = new int[pattern.length()];
        makeTable(pattern);
        kmp(pattern, parent);
    }
    static void makeTable(String pattern) {
        int idx = 0;
        for (int i = 1; i < pattern.length(); i++) {
            while (idx > 0 && pattern.charAt(idx) != pattern.charAt(i)) {
                idx = pi[idx-1];
            }
            if (pattern.charAt(idx) == pattern.charAt(i)) {
                idx++;
                pi[i] = idx;
            }
        }
    }

    static void kmp(String pattern, String parent) {
        int j = 0;
        for (int i = 0; i < parent.length(); i++) {
            while (j > 0 && pattern.charAt(j) != parent.charAt(i)) {
                j = pi[j-1];
            }
            if (pattern.charAt(j) == parent.charAt(i)) {
                if (j == pattern.length()-1) {
                    System.out.println(i-pattern.length()+2+"번째에서 찾았습니다");
                    break;
                }
                else
                    j++;
            }
        }
    }
}

 

 

참고

[알고리즘 정리] KMP, 문자열 패턴 매칭 알고리즘 (tistory.com)

[알고리즘 정리] KMP, 문자열 패턴 매칭 알고리즘

[문자열] KMP Algorithm | JusticeHui가 PS하는 블로그

[문자열] KMP Algorithm

30. KMP(Knuth-Morris-Pratt) 알고리즘 : 네이버 블로그 (naver.com)

30. KMP(Knuth-Morris-Pratt) 알고리즘