KMP 알고리즘

KMP란 ❓

특정 문자열에서 부분 문자열을 찾을 때 사용한다. KMP 알고리즘은 부분문자열을 찾는 알고리즘 중 유일하게 선형 시간복잡도를 가지기때문에 유명하다. 가령 문자열의 길이가 10^5 이고 패턴의 길이가 10^3일 때, 완전탐색 또는 다른 알고리즘의 최악의 경우 1억번 검사를 하게된다. 반면에 KMP알고리즘 같은경우, 101000번 검사로 패턴 매칭이 가능하다.

KMP의 기본 컨셉은 다음과같다.

• 문자열 패턴 불일치가 발생한 전체 문자열에서 어떤 부분 문자열이 일치했는지 알고있다.
• 불일치가 발생한 앞 부분에 대하여 다시 비교하지 않고 매칭을 수행한다.

즉, 매칭에 실패한 부분을 주목하지않고 매칭에 성공한 부분문자열에 주목을하자!

선행되어야 하는 것 🔑

접두사(prefix)와 접미사(suffix)

ABCDABA 의 접두사와 접미사를 구해보고 왜 필요한지 알아보자.

개수	접두사	접미사
1	A	A
2	AB	BA
3	ABC	ABA
4	ABCD	DABA
5	ABCDA	CDABA
6	ABCDAB	BCDABA
7	ABCDABA	ABCDABA

이 표를 통해서 접두사와 접미사가 무엇인지 파악할 수 있을것이다. 그렇다면 이 두가지 개념이 왜 필요할까?

그 이유는 pi[] 배열을 만들기 위해서이다.

pi[] 배열이란 ❓

pi[] 배열에는 문자열의 각 부분 문자열에서 접두사와 접미사가 같은 부분의(prefix == suffix) 개수를 저장하고있다. 아래 표를 통해서 이해해보자.

ABCDABA

i	부분 문자열	p[i]
0	A	0
1	AB	0
2	ABC	0
3	ABCD	0
4	ABCDA	1
5	ABCDAB	2
4	ABCDABA	1

pi 배열 구현 👇

    private static int[] getPi(String pattern) {
        int[] pi = new int[pattern.length()];
        char[] patterns = pattern.toCharArray();

        for (int i = 1, j = 0; i < pattern.length(); i++) {
            while(j > 0 && patterns[i] != patterns[j]) {
                    j = pi[j-1];
            }
            if (patterns[i] == patterns[j]) {
                pi[i] = ++j;
            }
        }
        return pi;
    }

KMP 구현 📌

구현 메커니즘은 다음과 같다.

• 원본 문자열의 길이만큼 순회하면서 부분 문자열을 비교한다.
• 만약 부분문자열과 다른 문자가 나온다면 pi[] 배열의 정보를 이용한다.
• pi[] 배열에 이전까지 비교했던 부분문자열중 일치했던 부분을 건너뛰고 그 다음부터 비교한다.

    private static void KMP(String text, String pattern) {
        int[] pi = getPi(pattern);
        char[] origin = text.toCharArray();
        char[] patterns = pattern.toCharArray();

        for (int i = 0, j = 0; i < text.length(); i++) {
            while(j > 0 && origin[i] != patterns[j]) {
                j = pi[j-1];
            }

            if(origin[i] == patterns[j]) {
                // 패턴 검색 성공
                if(j == pattern.length() - 1) {
                    System.out.println(i - patterns.length + 1);
                    j = pi[j];
                }
                else ++j;
            }
        }
    }