[Algorithm] C - KMP(Knuth-Morris-Pratt Algorithm) 알고리즘

요약

시간 복잡도 : 최상 O(mn)

• 문자열에서 특정 패턴을 미리 찾아내 검색하는 문자열 검색 알고리즘
• 문자열 검색 시 검사했던 위치 결과를 버러지 않아 효율적으로 검색할 수 있음
• 문자열 검색 시 불필요한 문자간 비교를 없애기 위해 실패 함수를 사용함
• Boyer-Moore 법과 성능이 같거나 좋지 않아 실제로 많이 사용되지 않는 알고리즘

KMP(Knuth-Morris-Pratt Algorithm) 알고리즘이란

KMP 알고리즘이란 문자열 중에서 특정 패턴을 찾아내는 문자열 검색 알고리즘 중 하나이다.
문자열 검색 시 검사했던 위치 결과를 버리지 않고 효율적으로 검색할 수 있는 특징이 있다.
문자열 검색 시 불필요한 문자간 비교를 없애기 위해서 실패 함수를 사용한다.

문자열 검색 방법

아래 예제는 "ZABCABXACCADEF" 에서 패턴 "ABCABD"를 검색하는 과정이다.
먼저 다음 그림과 같이 텍스트, 패턴의 첫 문자부터 순서대로 검사하고, 텍스트의 첫 문자 'Z'는 패턴에 없으므로 실패로 판단한다.

그 후 패턴을 1칸 뒤로 이동시키고, 패턴을 순서대로 검사하면 마지막 문자는 D로 검사할 문자열의 문자 'X'와 일치하지 않으므로 실패로 판단한다.

KMP법은 여기서 초록색 문자"AB"와 패턴의 "AB"가 일치한다는 점을 이용하는 것이다.
이 부분은 이미 검사를 마친 부분으로 검사할 문자열의 'X' 다음 문자부터 패턴의 "CABD"가 일치하는지만 검사하면 된다.

그래서 다음과 같이 "AB"와 'X'를 한 번에 3칸 이동시키고 세 번째 문자인 'C'부터 검사하면 된다.

이와 같이 KMP법은 텍스트와 패턴의 겹치는 부분을 찾아내어 검사를 다시 시작할 위치를 구하는 방법으로,
패턴을 최소의 횟수로 옮겨 알고리즘의 효율을 높인다.

하지만 몇 번째 문자부터 다시 검색을 시작할지 패턴을 이동시킬 때마다 다시 계산해야 한다면 효율이 높아지지 않는다.
그래서 몇 번째 문자부터 다시 검색할지에 대한 값을 미리 계산하여 문제를 해결한다.

계산 방법

먼저 찾을 패턴 안에서 중복되는 문자의 나열을 먼저 찾아야 하는데 이 과정에서 KMP법을 사용한다.
패턴 안에서 중복되는 문장의 나열을 찾기 위해 패턴의 첫 번째 문자가 서로 다른 경우
패턴을 1칸 뒤로 옮기고, 첫 번째 문자부터 다시 검사한다.

"ABDABD" 문자열 2개로 확인하는 예제

먼저 패턴 "ABDABD"를 1칸 뒤로 옮긴 다음 겹친다.
아래 그림을 보면 초록색 부분이 겹치지 않으므로, 패턴을 옮긴 다음 앞쪽의 첫 번째 문자부터 검사를 다시 시작해야 한다.
따라서 표에서 2번째 문자(B)의 값을 0으로 한다. 이 값이 0인 이유는 아래에 위시킨 패턴의 첫 번째 문자의 인덱스가 0이고,
이 위치에서 다시 검색을 시작하기 때문이다.

이후 다시 패턴을 1칸 뒤로 옮긴다. 다시 문자가 일치하지 않으므로 표에서 3번째 문자(C)의 값을 0으로 한다.

다시 패턴을 뒤로 옮기면 "AB"가 일치한다. 따라서 두 표에서 두 문자의 값을 1, 2로 지정할 수 있다.

이제 마지막으로 아래에 위치한 패턴을 2칸 뒤로 옮기면 일치하지 않으므로 D는 0값으로 지정한다.

이 과정에서 두 가지의 사실을 알 수 있다.

1. 패턴의 4번째 문자 'A'까지 일치한다면 아래에 위치한 패턴을 1칸 옮긴 다음 'A'를 건너뛰고 2번째 문자부터 검사할 수 있다.
2. 패턴의 5번째 문자 'B'까지 일치한다면 아래에 위치한 패턴을 1칸 옮긴 다음 "AB"를 건너 뛰고 3번째 문자부터 검사할 수 있다.

 

 

예제 코드

#include <stdio.h>

int KMP(const char *text, const char *partition);

int main() 
{
    int index;
    
    // 검색할 문자열 "ABABCDEFGHA"
    char s1[256];
    
    // 찾을 문자열 "ABC"
    char s2[256];
    
    printf("검색할 문자열 : ");
    scanf("%s", s1);
    
    printf("찾을 문자열 : ");
    scanf("%s", s2);
    
    index = KMP(s1, s2);
    
    if(index == -1) {
        printf("문자열 검색 실패!\n");
    }
    else {
        printf("%d 번째 문자부터 동일합니다.\n", index + 1);
    }

    return 0;
}

int KMP(const char *text, const char *partition)
{
    // text 커서
    int textCursor = 1;
    
    // partition 커서
    int partitionCursor = 0;
    
    // 건너뛸 표
    int skip[1024];
    
    skip[textCursor] = 0;
    
    while(partition[textCursor] != '\0') {
        if(partition[textCursor] == partition[partitionCursor]) {
            skip[++textCursor] = ++partitionCursor;
        }
        else if(partitionCursor == 0) {
            skip[++textCursor] = partitionCursor;
        }
        else {
            partitionCursor = skip[partitionCursor];
        }
    }
    
    textCursor = 0;
    partitionCursor = 0;
    
    while(text[textCursor] != '\0' && partition[partitionCursor] != '\0') {
        if(text[textCursor] == partition[partitionCursor]) {
            textCursor++;
            partitionCursor++;
        }
        else if(partitionCursor == 0) {
            textCursor++;
        }
        else {
            partitionCursor = skip[partitionCursor];
        }
    }
    
    if(partition[partitionCursor] == '\0') {
        return textCursor - partitionCursor;
    }
    
    return -1;
}

 

실행 결과

검색할 문자열 : ABABCDEFGHA
찾을 문자열 : ABC
3 번째 문자부터 동일합니다.

 

https://github.com/JeHeeYu/Algorithm/tree/main/String/KMP

GitHub - JeHeeYu/Algorithm: 알고리즘 개념 및 문제 풀이

 

 

출처 : Do it! 자료구조와 함께 배우는 알고리즘 입문: C 언어 편