[알고리즘] KMP(Knuth-Morris-Pratt) 알고리즘 - 코딩밥상

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

KMP 알고리즘은 '부르트 포스'처럼 탐색 위치를 본문 왼쪽부터 시작해서 오른쪽으로 옮겨가며 문자를 직접 비교하는 방식으로 작동합니다.

하지만 처음부터 끝까지 하나하나 모든 경우의 수를 다루는 부르트 포스 탐색과 달리 KMP 알고리즘은 비교할 필요 없는 부분은 지나치고 비교가 필요한 부분만 비교를 수행하는데에 차이점이 있습니다.

패턴과 본문 내 문자열을 한 차례 비교하고 나면, 다음 단계 탐색에서 사용할 수 있는 '정보'가 남으며 이 정보를 이용하면 불필요한 비교를 피할 수 있습니다. KMP 알고리즘은 이 '정보'가 무엇인지와 이 정보를 '어떻게 활용하는가'에 대한 것입니다.

---

KMP 알고리즘의 동작 방식

어느 문자열이든 접두부(Prefix/문자열의 머리 부분)와 접미부(suffix/문자열의 꼬리 부분)를 갖습니다.

예를들어 "BAABABAA" 문자열에서 얻을 수 있는 접두부와 접미부는 다음과 같습니다.

 

BAABABAA
접두부	접미부
B	A
BA	AA
BAA	BAA
BAAB	ABAA
BAABA	BABAA
BAABAB	ABABAA
BAABABA	AABABAA

이 중 같은 순서에 일치하는 접두부와 접미부는 빈 문자열과 BAA가 일치합니다. 

KMP 알고리즘에서는 빈 문자열이나 BAA처럼 문자열에서 일치하는 접두부와 접미부 쌍을 가리켜 '경계(Border)'라고 합니다.

이 경계를 활용해서 불필요한 문자 비교를 피합니다.

 

예를들어 다음과 같은 본문과 패턴을 탐색한다고 가정한다면

• 본문 : BAABAABAB
• 패턴 : BAABAB

본문과 패턴의 0~4번 문자열(BAABA)까지는 서로 일치합니다. 그런데 5번 문자에서 불일치가 발생합니다.

불일치가 발생하기 전까지 본문과 일치했던 패턴의 0~4번 문자열을 살펴보면 "BAABA"는 빈 문자열과 'BA' 2개의 경계를 갖습니다.

본문과 패턴이 0~4번까지 일치하기 때문에 이 구간에서 접두부와 접미부가 동일합니다. 따라서 패턴 전체를 오른쪽으로 쭉 밀어서 패턴의 접두부와 본문의 접미부를 일치하게 만들어주면 곧바로 5번부터 비교를 재개할 수 있게 됩니다.

이 때 패턴 탐색 위치 이동 거리는 일치하는 부분 문자열(BAABA)의 길이(5)에서 경계(BA)의 길이(2)를 뺀 값과 같습니다.

 

위와 같이 KMP 알고리즘은 사전에 파악해둔 패턴의 경계를 이용해 필요한 부분까지 뛰어 넘어 탐색을 재개합니다. 따라서 KMP알고리즘은 본문의 길이가 n일 때 최대 n번만큼만 비교를 수행하면 본문에서 패턴과 일치하는 문자열의 위치를 알 수 있습니다.

 

경계 정보 계산 방법

위 과정을 이해하고 또 다시 궁금증이 생겼습니다. 그렇다면 경계(Border)를 먼저 알아야겠네.

KMP 알고리즘은 탐색을 수행하기 전에 미리 패턴으로부터 경계의 정보를 가진 테이블을 만듭니다.

이번에는 "BAABABAA"라는 패턴으로 경계 테이블을 만들어 보겠습니다.

 

일치 접두부의 길이		0	1	2	3	4	5	6	7	8
문자열		B	A	A	B	A	B	A	A
일치 접두부의 최대 경계 넓이		-1	0	0	0	1	2	1	2	3

첫 번째 문자부터 불일치가 일어난다고 가정해봅시다. 불일치가 일어난 위치 이전의 일치 접두부에서 최대 경계를 찾기 때문에 이 경우 일치 접두부가 아예 존재하지 않습니다. 따라서 첫 번째 문자의 경계 넓이는 항상 -1입니다. 왜 0이 아닌 -1이냐 하면 0은 이전 접두부가 존재하지만 경계가 없을 때 경계의 넓이로 사용하기 때문에 차이점을 둬야합니다.

 

두 번째 문자에서 불일치가 일어난다면 일치 접두부는 B하나이기에 경계가 존재하지 않으므로 최대 경계 넓이는 0이 됩니다.

 

세 번째, 네 번째 역시 경계는 빈 문자열만 존재하기 때문에 최대 경계의 넓이는 0이 되겠네요.

 

다섯 번째 문자에서 불일치가 발생한 경우 일치 접두부는 BAAB이므로 최대 경계가 B이며 넓이는 1입니다.

 

여섯 번째 문자의 일치 접두부는 BAABA이므로 최대 경계는 BA이며 넓이는 2입니다.

 

일곱 번째 문자의 일치 접두부는 BAABAB이므로 최대 경계는 B이며 넓이는 1입니다.

 

여덟 번째 문자의 일치 접두부는 BAABABA이므로 최대 경계는 BA이며 넓이는 2입니다.

 

아홉 번째 문자의 일치 접두부는 BAABABAA이므로 최대 경계는 BAA이며 넓이는 3입니다. 이는 본문 내 문자열이 패턴과 일치하지만, 탐색을 이어서 계속하고자 할 때 사용합니다. 

 

여기까지 탐색 위치의 이동 거리를 계산하기 위해 경계 테이블을 만들었으니 사용만 하면 됩니다. 즉 불일치가 발생했을 때 탐색 위치의 이동 거리는 다음 식을 이용하면 계산할 수 있습니다.

이동 거리 = 일치 접두부의 길이 - 최대 경계 넓이

---

구현

void Preprocess(char* Pattern, int PatternSize, int* Border){
    int i = 0;
    int j = -1;
    Border[0] = -1;
    
    while(i < PatternSize){
        while(j>-1 && Pattern[i] != Pattern[j]) j = Border[j];
        
        i++;
        j++;
        
        Border[i] = j;
    }
}

int KnuthMorrisPratt(char* Text, int TextSize, int Start, char* Pattern, int PatternSize){
    int i = Start;
    int j = 0;
    int Position = -1;
    
    int* Border = (int*)calloc(PatternSize + 1, sizeof(int));
    
    Preprocess(Pattern, PatternSize + 1, Border);
    
    while(i < TextSize){
        while(j>=0 && Text[i]!=Pattern[j])  j = Border[j];
        
        i++;
        j++;
        
        if(j == PatternSize){
            Position = i-j;
            break;
        }
    }
    
    free(Border);
    return Position;
}