[JAVA] KMP 알고리즘(문자열 검색)

문자열 검색을 하는 가장 기본적인 방법은 pattern(len : M) 문자열을 target(len : N) 문자열 각 인덱스마다 각각 하나씩 확인하는 방법이다. 이 경우 시간복잡도는 N(NM)이 된다.

하지만 KMP 알고리즘을 이용하면 시간 복잡도 O(N+M)으로 엄청나게 효율적으로 문자열을 찾을 수 있다고 한다.

 

import java.util.Arrays;

class KMP {

    static int[] makeTable(char[] p) {
        int psize = p.length;
        int[] table = new int[psize];
        int j = 0;
        for (int i = 1; i < psize; i++) {
            while (j > 0 && p[i] != p[j]) {
                j = table[j - 1];
            }
            if (p[i] == p[j]) {
                table[i] = ++j;
            }
        }
        return table;
    }

    static void kmp(char[] parent, char[] pattern) {
        int[] table = makeTable(pattern);
        int parentSize = parent.length;
        int patternSize = pattern.length;
        int j = 0;
        for (int i = 0; i < parentSize; i++) {
            while (j > 0 && parent[i] != pattern[j]) {
                j = table[j - 1];
            }
            if (parent[i] == pattern[j]) {
                if (j == patternSize - 1) {
                    System.out.printf("%d. \n", i - patternSize + 1);
                    j = table[j];
                } else {
                    j++;
                }
            }
        }
    }

    public static void main(String[] args) {
        char[] parent = "ababacabacaabacaaba".toCharArray();
        char[] pattern = "abacaaba".toCharArray();
        System.out.println("target : " + Arrays.toString(parent));
        System.out.println("pattern : " + Arrays.toString(pattern));
        kmp(parent, pattern);
    }

}

 

 

결과 화면

 

https://blog.naver.com/ndb796/221240660061

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

https://bowbowbow.tistory.com/6

KMP : 문자열 검색 알고리즘