KMP 문자열 매칭 알고리즘 vs 순차 탐색 알고리즘

---

1. 문자열 매칭 알고리즘 (KMP 알고리즘)

문자열 매칭 알고리즘에 대해서 알아보겠습니다.

먼저 문자열 매칭을 위해서는 단순 반복을 통하여 문자열을 찾아 낼 수 있는 방법이 있습니다.

이를 java로 구현해 보겠습니다.

package idea;

public class SimpleComparisonString {
    /**
     * 단순 문자열 찾기 알고리즘
     * KMP 라는 더 효율적인 알고리즘을 사용 하기 전에 구현
     * @참고 https://blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221240660061&categoryNo=128&parentCategoryNo=0&viewDate=&currentPage=4&postListTopCurrentPage=1&from=postList&userTopListOpen=true&userTopListCount=5&userTopListManageOpen=false&userTopListCurrentPage=4
     */
    public static void main(String[] args) {
        String parent = "Hello world";
        String pattern = "llo w";
        int result = findString(parent, pattern);
        if (result == -1)
            System.out.printf("찾을수 없습니다.");
        else
            System.out.printf("%d번째에서 찾았습니다.", result + 1);
    }

    static int findString(String parent, String pattern) {
        char[] parents = parent.toCharArray();
        char[] patterns = pattern.toCharArray();
        int index = -1;

        for (int i = 0; i < parents.length - patterns.length; i++) {
            boolean finded = true;
            for (int k = 0; k < patterns.length; k++) {
                if (parents[i + k] != patterns[k]) {
                    finded = false;
                    break;
                }
            }
            if (finded) {
                index = i;
                break;
            }
        }

        return index;
    }
}

이런식으로 단순히 부모 문자열과 패턴 문자열을 단순 순회 하면서 패턴 문자열이 존재하는지 확인 할 수 있습니다.

하지만! 이런 방법으로 구현 할 시에 시간 복잡도 : O( N * M ) -> 부모 문자열의 수 * 패턴 문자열의 수 가 됩니다. 이런 경우 시간을 줄이기 위해서 KMP (Knuth-Morris-Pratt) 라는 알고리즘을 사용 할 수 있는데요!

​

 

1. 이런 식으로 패턴의 접두사와 접미사의 일치 길이를 알면

​

 

2. 위 그림 처럼 (미스매치 전 까지의 패턴 갯수 - 일치한 접미사의 수) 만큼 뒤로 이동을 할 수 있습니다. 이를 최대 일치 길이 테이블 이라고 합니다. java로 최대 일치 길이 테이블을 구현해 보겠습니다.

static int[] makeTable(String pattern) {
        char[] patterns = pattern.toCharArray();
        int[] table = new int[patterns.length];
        Arrays.fill(table, 0);
        int k = 0;
        for (int i = 1; i < patterns.length; i++) {
            while (k > 0 && patterns[i] != patterns[k]) {
                k = table[k - 1];
            }
            if (patterns[i] == patterns[k]) {
                table[i] = ++k;
            }
        }
        return table;
    }

 

 

2. 이제 최대 일치 길이 테이블을 토대로 문자열 매칭 알고리즘 KMP를 구현 할 수 있습니다.

package idea;

import java.util.Arrays;

public class KMP {
    /**
     * @참고 https://blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221240660061&categoryNo=128&parentCategoryNo=0&viewDate=&currentPage=4&postListTopCurrentPage=1&from=postList&userTopListOpen=true&userTopListCount=5&userTopListManageOpen=false&userTopListCurrentPage=4
     * @내용 KMP (Knuth-Morris-Pratt) 알고리즘 : 문자열 매칭 알고리즘
     */
    public static void main(String[] args) {
        String parent = "ababacabacaabacaaba";
        String pattern = "abacaaba";
        kmp(parent, pattern);
    }

    static void kmp(String parent, String pattern) {
        int[] table = makeTable(pattern);
        char[] parents = parent.toCharArray();
        char[] patterns = pattern.toCharArray();
        int k = 0;
        for (int i = 0; i < parents.length; i++) {
            while (k > 0 && parents[i] != patterns[k]) {
                k = table[k - 1];
            }
            if (parents[i] == patterns[k]) {
                if (k == patterns.length - 1) {
                    System.out.printf("%d번째에서 찾았습니다.\n", i - patterns.length + 2);
                    k = table[k];
                } else {
                    k++;
                }
            }
        }
    }

    static int[] makeTable(String pattern) {
        char[] patterns = pattern.toCharArray();
        int[] table = new int[patterns.length];
        Arrays.fill(table, 0);
        int k = 0;
        for (int i = 1; i < patterns.length; i++) {
            while (k > 0 && patterns[i] != patterns[k]) {
                k = table[k - 1];
            }
            if (patterns[i] == patterns[k]) {
                table[i] = ++k;
            }
        }
        return table;
    }
}