문자열 매칭 알고리즘 KMP와 라빈-카프

문자열 매칭 알고리즘은 컴퓨터 과학에서 매우 중요한 문제 중 하나로, 특정 패턴을 주어진 텍스트에서 빠르고 효율적으로 찾는 것이 목표입니다. 문자열 매칭 알고리즘은 검색 엔진, 데이터베이스, DNA 서열 분석 등 다양한 응용 분야에서 사용됩니다. 이번 포스팅에서는 대표적인 문자열 매칭 알고리즘인 KMP(Knuth-Morris-Pratt) 알고리즘과 라빈-카프(Rabin-Karp) 알고리즘을 Java와 C 예제를 통해 설명해 보겠습니다.

1. KMP 알고리즘

KMP 알고리즘은 부분 일치 테이블(또는 접두사 함수)을 사용하여 텍스트 내에서 패턴을 효율적으로 검색합니다. 일반적인 브루트포스 방식은 텍스트 내의 모든 위치에서 패턴을 비교하지만, KMP는 불필요한 비교를 줄이는 방식으로 효율성을 높입니다.

KMP 알고리즘의 동작 원리

KMP 알고리즘은 두 가지 주요 단계로 나뉩니다.

1. 부분 일치 테이블 생성: 패턴의 각 위치에서 얼마나 중복되는 접두사와 접미사가 있는지를 기록한 테이블을 만듭니다.
2. 패턴 검색: 부분 일치 테이블을 사용하여 텍스트에서 패턴을 빠르게 찾아냅니다. 만약 일치하지 않는 문자가 나오면, 이미 계산된 테이블을 이용해 다음 비교 위치로 빠르게 이동합니다.

KMP 알고리즘 Java 구현

public class KMP {
    public static void main(String[] args) {
        String text = "abxabcabcaby";
        String pattern = "abcaby";
        kmpSearch(text, pattern);
    }

    public static void kmpSearch(String text, String pattern) {
        int[] lps = computeLPSArray(pattern);
        int i = 0, j = 0;
        while (i < text.length()) {
            if (pattern.charAt(j) == text.charAt(i)) {
                i++;
                j++;
            }
            if (j == pattern.length()) {
                System.out.println("패턴 발견: 인덱스 " + (i - j));
                j = lps[j - 1];
            } else if (i < text.length() && pattern.charAt(j) != text.charAt(i)) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
    }

    public static int[] computeLPSArray(String pattern) {
        int[] lps = new int[pattern.length()];
        int length = 0;
        int i = 1;
        lps[0] = 0;
        while (i < pattern.length()) {
            if (pattern.charAt(i) == pattern.charAt(length)) {
                length++;
                lps[i] = length;
                i++;
            } else {
                if (length != 0) {
                    length = lps[length - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }
}

KMP 알고리즘 C 구현

#include <stdio.h>
#include <string.h>

void computeLPSArray(char* pattern, int M, int* lps);
void KMPSearch(char* pattern, char* text) {
    int M = strlen(pattern);
    int N = strlen(text);
    int lps[M];
    computeLPSArray(pattern, M, lps);
    int i = 0, j = 0;
    while (i < N) {
        if (pattern[j] == text[i]) {
            i++;
            j++;
        }
        if (j == M) {
            printf("패턴 발견: 인덱스 %d\n", i - j);
            j = lps[j - 1];
        } else if (i < N && pattern[j] != text[i]) {
            if (j != 0)
                j = lps[j - 1];
            else
                i++;
        }
    }
}

void computeLPSArray(char* pattern, int M, int* lps) {
    int length = 0;
    lps[0] = 0;
    int i = 1;
    while (i < M) {
        if (pattern[i] == pattern[length]) {
            length++;
            lps[i] = length;
            i++;
        } else {
            if (length != 0) {
                length = lps[length - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

int main() {
    char text[] = "abxabcabcaby";
    char pattern[] = "abcaby";
    KMPSearch(pattern, text);
    return 0;
}

2. 라빈-카프 알고리즘

라빈-카프 알고리즘은 해시 함수를 이용하여 패턴을 검색하는 방법입니다. 해시 함수를 사용해 패턴과 텍스트의 부분 문자열을 숫자로 변환한 후, 이 숫자들을 비교하여 일치 여부를 확인합니다. 만약 해시 값이 일치하면, 실제 문자열도 일치하는지 확인합니다. 이 방법은 충돌 가능성이 있지만, 평균적인 경우 매우 빠르게 작동합니다.

라빈-카프 알고리즘의 동작 원리

1. 해시 값 계산: 패턴과 텍스트의 첫 부분에 대해 해시 값을 계산합니다.
2. 해시 값 비교: 패턴의 해시 값과 텍스트의 현재 부분 문자열의 해시 값을 비교합니다.
3. 충돌 처리: 해시 값이 일치할 경우 실제 문자열이 동일한지 확인합니다.
4. 슬라이딩: 다음 부분 문자열로 이동하며 해시 값을 업데이트합니다.

라빈-카프 알고리즘 Java 구현

public class RabinKarp {
    public static void main(String[] args) {
        String text = "GEEKS FOR GEEKS";
        String pattern = "GEEK";
        int q = 101; // 소수 값
        search(pattern, text, q);
    }

    public static void search(String pattern, String text, int q) {
        int d = 256;
        int M = pattern.length();
        int N = text.length();
        int i, j;
        int p = 0; // 패턴의 해시 값
        int t = 0; // 텍스트의 해시 값
        int h = 1;

        for (i = 0; i < M - 1; i++)
            h = (h * d) % q;

        for (i = 0; i < M; i++) {
            p = (d * p + pattern.charAt(i)) % q;
            t = (d * t + text.charAt(i)) % q;
        }

        for (i = 0; i <= N - M; i++) {
            if (p == t) {
                for (j = 0; j < M; j++) {
                    if (text.charAt(i + j) != pattern.charAt(j))
                        break;
                }
                if (j == M)
                    System.out.println("패턴 발견: 인덱스 " + i);
            }
            if (i < N - M) {
                t = (d * (t - text.charAt(i) * h) + text.charAt(i + M)) % q;
                if (t < 0)
                    t = (t + q);
            }
        }
    }
}

라빈-카프 알고리즘 C 구현

#include <stdio.h>
#include <string.h>

#define d 256

void rabinKarp(char* pattern, char* text, int q) {
    int M = strlen(pattern);
    int N = strlen(text);
    int p = 0;
    int t = 0;
    int h = 1;
    int i, j;

    for (i = 0; i < M - 1; i++)
        h = (h * d) % q;

    for (i = 0; i < M; i++) {
        p = (d * p + pattern[i]) % q;
        t = (d * t + text[i]) % q;
    }

    for (i = 0; i <= N - M; i++) {
        if (p == t) {
            for (j = 0; j < M; j++) {
                if (text[i + j] != pattern[j])
                    break;
            }
            if (j == M)
                printf("패턴 발견: 인덱스 %d\n", i);
        }
        if (i < N - M) {
            t = (d * (t - text[i] * h) + text[i + M]) % q;
            if (t < 0)
                t = (t + q);
        }
    }
}

int main() {
    char text[] = "GEEKS FOR GEEKS";
    char pattern[] = "GEEK";
    int q = 101;
    rabinKarp(pattern, text, q);
    return 0;
}

결론

이번 포스팅에서는 문자열 매칭 문제를 해결하기 위한 두 가지 대표적인 알고리즘, KMP와 라빈-카프 알고리즘을 소개했습니다. KMP는 부분 일치 테이블을 사용하여 불필요한 비교를 줄이는 반면, 라빈-카프는 해시를 이용하여 빠르게 패턴을 검색합니다. 각각의 알고리즘은 상황에 따라 장단점이 있으며, 알고리즘의 특성을 이해하고 적절하게 선택하는 것이 중요합니다.