[문자열] KMP 알고리즘

KMP 알고리즘이란?

『KMP 알고리즘』 문자열을 검색할 때, 불필요한 반복을 줄이기 위해

검색 문자열의 접두사와 접미사의 중복 길이를 이용한 알고리즘 입니다. 

(※ Knuth–Morris–Pratt algorithm, KMP)

 

 

[Case] 문자열을 검색할 때 비효율적인 알고리즘 

A = aab, B = aaaaaaaaaa

비교 문자열 (A)를 대상 (B)와 일일이 비교하는 경우입니다.

결과적으로 위의 경우에는 문자열 A, B는 같은 구간이 없지만,

(A) 문자열 『aab』 에서 『b』를 제외하고는 B문자열과 일치하기에 (A) 문자열 전체로 불필요한 비교를 하게 됩니다.

문자열 A의 길이가 N / 문자열 B의 길이가 M일 때, 결과적으로 O(NM)의 시간을 가집니다.

※ 관련 문제:   [BOJ] 1120 문자열

[BOJ] 백준 1120 문자열

 

이는 비교 문자열 A를 한 칸씩 움직이기 때문입니다.

위(↑)와 같이 일치하지 않을 때, 한 칸씩 이동하지 않고 바로 아래(↓)와 같이 일정 구간을 건너갈 수 없을까?

일치하지 않은 지점에서 한 칸 이동해봐야 무의미하므로

미리 구해놓은 일정 구간을 건너 뛰어 검색하는 것이다.

 

KMP 알고리즘 구현

① 실패 함수(Failure Function) 구현

불일치가 발생했을 때, 어느 정도 건너뛰는지 나타내는 지표.

패턴 문자열 P 가 주어졌을 때, 접두사 접미사의 최대 일치 길이를 구합니다.

private static int[] makeTable(String patternStr) {
    // 테이블 배열 생성
    char[] pattern = patternStr.toCharArray();
    int pLen = pattern.length;
    int[] table = new int[pLen];
    
    int j = 0;
    for(int i=1; i<pLen; i++) {
        while(j>0 && pattern[i] != pattern[j]) {
            j = table[j-1];
        }
        if(pattern[i] == pattern[j]) {
            table[i] = ++j;
        }
    }
    return table;
}

　

② 구한 테이블을 이용해 문자열 매칭 작업을 합니다.

private static List<Integer> KMP(char[] text, char[] pattern) {
    int[] table = makeTable(pattern);
    int textSize = text.length;
    int patternSize = pattern.length;
    
    // 매칭되는 인덱스 위치
    List<Integer> matchingIndexArr = new ArrayList<Integer>();
    
    int j = 0;
    for(int i=0; i<textSize; i++) {
        // 실패 함수 테이블에 저장된 값으로 이동
        while(j > 0 && text[i] != pattern[j]) {
            j = table[j-1];
        }
        if(text[i] == pattern[j]) {
            // 패턴 매칭 성공
            if(j == patternSize - 1) {
                // 매칭되는 위치 인덱스 저장
                matchingIndexArr.add(i - patternSize + 2);
                j = table[j];
            }
            else {
                j++;
            }
        }
    }
    return matchingIndexArr;
}

 

Q. while문 조건에 j > 0은 왜필요할까?

while(j > 0 && p[i] != p[j]) {
    j = pi[j-1];
}

『일치했던 정보를 이용해서 점프하는 것』 을 구현한 부분으로,

이 때 "한 글자 라도 일치한 것"이 있어야 "그 정보를 이용해서 점프"를 할 수 있을텐데

j > 0 조건이 "한 글자 라도 일치한 것이 있냐"를 확인하는 조건입니다.

 

Reference

- [BOJ] 1120 문자열

- [BOJ] 1786 찾기