C언어로 구현하는 KMP 알고리즘: 문자열 패턴 검색 완벽 가이드

이 문제에서는 텍스트(text)와 패턴(pattern) 두 개의 문자열이 주어집니다. 우리의 과제는 KMP 알고리즘을 이용한 패턴 검색 프로그램을 작성하여, 텍스트 문자열 내에서 패턴이 나타나는 모든 위치를 찾아내는 것입니다.

즉, 텍스트 안에 패턴이 등장하는 모든 인덱스를 출력해야 합니다.

문제 이해를 위한 예시

입력

text = "xyztrwqxyzfg" pattern = "xyz"

출력

Found at index 0
Found at index 7

위 예시에서 패턴 "xyz"는 텍스트의 0번째 인덱스와 7번째 인덱스에서 발견됩니다.

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

KMP(Knuth Morris Pratt) 알고리즘은 단순 브루트 포스 방식보다 효율적으로 문자열에서 패턴을 찾는 알고리즘입니다. 핵심 아이디어는 패턴에 대한 사전 처리(preprocessing)를 수행하여, 매칭 과정에서 불일치가 발생했을 때 이미 비교한 정보를 재활용하는 것입니다.

일반적인 방법에서는 불일치가 발생하면 텍스트 포인터를 한 칸 뒤로 물러나 다시 처음부터 비교해야 하지만, KMP 알고리즘은 이를 피할 수 있습니다. 특히 일부 문자가 일치한 후 불일치가 발생하는 상황에서도 텍스트 포인터를 되돌리지 않고 계속 진행할 수 있어 시간 복잡도가 크게 개선됩니다.

접두사-접미사 배열(실패 함수)

KMP 알고리즘은 패턴을 사전 처리하여 적절한 접두사(proper prefix)와 접미사(suffix)가 일치하는 최대 길이를 저장하는 배열을 만듭니다. 이 배열(흔히 실패 함수 또는 LPS 배열이라고 부름)은 불일치가 발생했을 때 패턴 내에서 어느 위치부터 비교를 재개하면 되는지 알려주므로, 불필요한 중복 비교를 제거합니다.

시간 복잡도: O(N + M) — N은 텍스트 길이, M은 패턴 길이
공간 복잡도: O(M) — 접두사-접미사 배열 저장 공간

C 언어로 구현한 KMP 패턴 검색 프로그램

다음은 C 언어로 작성된 KMP 알고리즘 전체 코드입니다.

예제 코드

#include<iostream>
#include<string.h>
using namespace std;
void prefixSuffixArray(char* pat, int M, int* pps) {
    int length = 0;
    pps[0] = 0;
    int i = 1;
    while (i < M) {
        if (pat[i] == pat[length]) {
            length++;
            pps[i] = length;
            i++;
        } else {
            if (length != 0)
                length = pps[length - 1];
            else {
                pps[i] = 0;
                i++;
            }
        }
    }
}
void KMPAlgorithm(char* text, char* pattern) {
    int M = strlen(pattern);
    int N = strlen(text);
    int pps[M];
    prefixSuffixArray(pattern, M, pps);
    int i = 0;
    int j = 0;
    while (i < N) {
        if (pattern[j] == text[i]) {
            j++;
            i++;
        }
        if (j == M) {
            printf("Found pattern at index %d\n", i - j);
            j = pps[j - 1];
        }
        else if (i < N && pattern[j] != text[i]) {
            if (j != 0)
                j = pps[j - 1];
            else
                i = i + 1;
        }
    }
}
int main() {
    char text[] = "xyztrwqxyzfg";
    char pattern[] = "xyz";
    printf("The pattern is found in the text at the following index : \n");
    KMPAlgorithm(text, pattern);
    return 0;
}

코드 설명

prefixSuffixArray 함수는 패턴의 각 위치별로 접두사와 접미사가 일치하는 최대 길이를 계산하여 pps 배열에 저장합니다. KMPAlgorithm 함수는 이 배열을 활용해 텍스트를 한 번만 순회하면서 패턴과 일치하는 모든 위치를 찾아냅니다. 패턴 전체가 일치하면 해당 시작 인덱스를 출력하고, j 값을 조정하여 겹치는 패턴도 놓치지 않고 탐색을 계속합니다.

실행 결과

프로그램을 실행하면 다음과 같은 결과가 출력됩니다.

The pattern is found in the text at the following index :
Found pattern at index 0
Found pattern at index 7

이처럼 KMP 알고리즘을 사용하면 텍스트를 한 번만 순회하면서도 모든 패턴 발생 위치를 효율적으로 찾을 수 있습니다. 대용량 텍스트 검색이나 반복적인 패턴이 많은 경우 특히 유용한 알고리즘입니다.