이 문제에서는 텍스트(text)와 패턴(pattern), 두 개의 문자열이 주어집니다. 우리의 과제는 라빈-카프(Rabin-Karp) 알고리즘을 활용한 패턴 검색 프로그램을 작성하여, 텍스트 문자열 안에서 패턴이 나타나는 모든 위치를 찾아내는 것입니다.
예시를 통해 문제를 이해해 보겠습니다.
입력 예시
text = "xyztrwqxyzfg" pattern = "xyz"
출력 결과
Found at index 0 Found at index 7
텍스트 "xyztrwqxyzfg" 안에서 패턴 "xyz"는 인덱스 0과 인덱스 7, 두 곳에서 발견됩니다.
라빈-카프 알고리즘의 동작 원리
라빈-카프 알고리즘은 해싱(hash) 기반의 문자열 검색 기법입니다. 기본적인 아이디어는 다음과 같습니다.
먼저 텍스트 문자열 위에 패턴과 같은 크기의 윈도우(window)를 만들고, 이 윈도우를 한 칸씩 오른쪽으로 밀면서 이동합니다. 각 위치에서 윈도우 내 부분 문자열의 해시값을 계산한 뒤, 패턴의 해시값과 비교합니다. 두 해시값이 일치하면 실제로 문자 하나하나가 모두 일치하는지 추가로 확인하여 오탐(false positive)을 방지합니다.
여기서 핵심은 롤링 해시(rolling hash)입니다. 윈도우가 이동할 때 전체 해시값을 다시 계산하는 대신, 빠져나간 문자와 새로 들어온 문자만 반영하여 해시값을 상수 시간에 갱신할 수 있습니다.
해시값을 만드는 방식은 각 문자의 숫자 값(ASCII 코드 등)을 자릿수 가중치와 함께 더하고, 값이 너무 커지지 않도록 소수(prime number)로 나눈 나머지를 취하는 것입니다. 소수를 사용하면 서로 다른 문자열이 같은 해시값을 가질 확률(해시 충돌)을 줄일 수 있습니다.
C 언어로 구현한 라빈-카프 알고리즘
다음은 C 언어로 작성한 완전한 구현 코드입니다.
#include <stdio.h>
#include <string.h>
#define c 256
void search(char pattern[], char text[]){
int M = strlen(pattern);
int N = strlen(text);
int i, j;
int hashP = 0;
int hashT = 0;
int h = 1;
for (i = 0; i < M - 1; i++)
h = (h * c) % 103;
for (i = 0; i < M; i++) {
hashP = (c * hashP + pattern[i]) % 103;
hashT = (c * hashT + text[i]) % 103;
}
for (i = 0; i <= N - M; i++) {
if (hashP == hashT) {
for (j = 0; j < M; j++) {
if (text[i + j] != pattern[j])
break;
}
if (j == M)
printf("Pattern found at index %d \n", i);
}
if (i < N - M) {
hashT = (c * (hashT - text[i] * h) + text[i + M]) % 103;
if (hashT < 0)
hashT = (hashT + 103);
}
}
}
int main(){
char text[] = "xyztrwqxyzfg";
char pattern[] = "xyz";
printf("The pattern is found in the text at the following index : \n");
search(pattern, text);
return 0;
}코드 주요 단계 설명
1. 초기 해시값 계산: 패턴 길이 M에 대해 h = 256^(M-1) mod 103 값을 미리 계산해 둡니다. 이 값은 롤링 해시 시 맨 앞 문자의 기여도를 제거할 때 사용됩니다.
2. 패턴 및 첫 윈도우의 해시 계산: 패턴 전체와 텍스트의 첫 M개 문자에 대해 해시값 hashP와 hashT를 각각 계산합니다.
3. 슬라이딩 윈도우 순회: 텍스트를 처음부터 끝까지 이동하며 해시값을 비교하고, 일치하면 문자 단위 검증 후 위치를 출력합니다.
4. 롤링 해시 갱신: 윈도우를 한 칸 밀 때 이전 해시값에서 맨 앞 문자의 영향을 제거하고 새 문자를 추가합니다. 음수가 되는 경우 소수인 103을 더해 양수로 보정합니다.
실행 결과
위 프로그램을 실행하면 다음과 같은 출력을 얻을 수 있습니다.
The pattern is found in the text at the following index : Pattern found at index 0 Pattern found at index 7
마무리
라빈-카프 알고리즘은 평균적으로 O(N+M)의 시간 복잡도로 동작하며, 최악의 경우 O(N×M)까지 느려질 수 있지만, 다중 패턴 검색이나 플래그어리즘 탐지처럼 해시 비교가 유리한 상황에서 특히 강력한 성능을 발휘합니다. 단순한 브루트 포스 방식보다 불필요한 문자 비교를 크게 줄일 수 있다는 점이 가장 큰 장점입니다.