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

KMP 알고리즘 이란

주어진 텍스트 문자열에서 특정 패턴 문자열이 등장하는 위치를 효율적으로 찾는 데 사용됩니다. KMP 알고리즘은 패턴 매칭의 각 단계에서 이미 비교된 정보를 활용하여 불필요한 비교를 줄임으로써 검색 속도를 높이는 방식으로 작동합니다.

KMP 알고리즘 구현 코드

public class KMP {
    
    // KMP 알고리즘을 사용하여 패턴을 검색하는 메서드
    public static void KMPSearch(String pattern, String text) {
        int M = pattern.length();
        int N = text.length();
        
        // 부분 일치 테이블을 생성합니다.
        int[] lps = new int[M];
        computeLPSArray(pattern, M, lps);
        
        int i = 0;  // 텍스트의 인덱스
        int j = 0;  // 패턴의 인덱스
        while (i < N) {
            if (pattern.charAt(j) == text.charAt(i)) {
                j++;
                i++;
            }
            if (j == M) {
                System.out.println("Found pattern at index " + (i - j));
                j = lps[j - 1];
            } else if (i < N && pattern.charAt(j) != text.charAt(i)) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i = i + 1;
                }
            }
        }
    }
    
    // 패턴 문자열에 대한 부분 일치 테이블을 계산하는 메서드
    public static void computeLPSArray(String pattern, int M, int[] lps) {
        int length = 0;  // 이전 길이를 저장하는 변수
        int i = 1;
        lps[0] = 0;  // lps[0]은 항상 0
        
        // 패턴의 나머지 부분에 대해 lps를 계산합니다.
        while (i < M) {
            if (pattern.charAt(i) == pattern.charAt(length)) {
                length++;
                lps[i] = length;
                i++;
            } else {
                if (length != 0) {
                    length = lps[length - 1];
                } else {
                    lps[i] = length;
                    i++;
                }
            }
        }
    }

    // 메인 메서드
    public static void main(String[] args) {
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";
        KMPSearch(pattern, text);
    }
}

KMP 알고리즘의 원리

1. 사전 처리 단계: 패턴 문자열을 분석하여 접두사와 접미사가 일치하는 부분을 기록한 "부분 일치 테이블(LSP Table)"을 생성합니다. 이 테이블은 패턴의 각 위치에서 매칭 실패 시 이동할 위치를 지정합니다.

 

부분 일치 테이블(LPS) 생성 원리

부분 일치 테이블은 패턴의 접두사와 접미사가 일치하는 최대 길이를 기록한 배열입니다. 이를 통해, 매칭이 실패할 때 패턴의 어느 부분으로 돌아가야 할지 결정할 수 있습니다.

예를 들어, 패턴이 "ABABCABAB"라면, 부분 일치 테이블은 다음과 같이 계산됩니다:

1. lps[0] = 0: 항상 0입니다. 
2. i = 1, pattern[1] == pattern[0] ("B" != "A") → lps[1] = 0
3. i = 2, pattern[2] == pattern[0] ("A" == "A") → lps[2] = 1    *ABA에서 접두사 A, 접미사 A
4. i = 3, pattern[3] == pattern[1] ("B" == "B") → lps[3] = 2  *ABAB에서 접두사 AB, 접미사 AB
5. i = 4, pattern[4] == pattern[2] ("C" != "A") → lps[4] = 0   *ABABC에서 일치하는 접두사 접미사 없음 
6. i = 5, pattern[5] == pattern[0] ("A" == "A") → lps[5] = 1    ....
7. i = 6, pattern[6] == pattern[1] ("B" == "B") → lps[6] = 2.   ....
8. i = 7, pattern[7] == pattern[2] ("A" == "A") → lps[7] = 3.   ....
9. i = 8, pattern[8] == pattern[3] ("B" == "B") → lps[8] = 4.  ABABCABAB에서 접두사 ABAB, 접미사 ABAB

 

2. 검색 단계: 텍스트 문자열을 순차적으로 스캔하면서 패턴 문자열과 비교합니다. 매칭 실패 시 부분 일치 테이블을 참조하여 패턴의 위치를 이동시킵니다. 

Brute Force와의 비교

Brute Force로 문자열을 하나씩 비교하려면  O(n * m)이 걸리는데 반해 (n은 텍스트 문자열의 길이, m은 패턴 문자열의 길이)

KMP 알고리즘의 시간 복잡도는 O(n + m)으로, 매우 효율적입니다.