C 언어에서의 패턴 매칭(Pattern Matching)이란 하나의 문자열 안에 다른 문자열이 존재하는지 찾는 작업을 의미합니다. 예를 들어, "naive algorithm"이라는 문자열 안에 "algorithm"이라는 문자열이 포함되어 있는지 확인하고, 발견되면 해당 위치(인덱스)를 출력하는 것입니다. 이를 위해 두 개의 문자 배열을 입력받아 매칭에 성공하면 위치를 반환하고, 실패하면 -1을 반환하는 함수를 작성할 수 있습니다.
입력: txt = "HERE IS A NICE CAP"
pattern = "NICE"
출력: 인덱스 10에서 패턴 발견
입력: txt = "XYZXACAADXYZXYZX"
pattern = "XYZX"
출력: 인덱스 0에서 패턴 발견
인덱스 9에서 패턴 발견
인덱스 12에서 패턴 발견라빈-카프(Rabin-Karp) 알고리즘이란?
라빈-카프 알고리즘은 Rabin과 Karp가 제안한 문자열 매칭 알고리즘으로, 기존의 나이브(Naive) 알고리즘보다 더 효율적으로 패턴을 찾을 수 있도록 설계되었습니다.
나이브 알고리즘과 마찬가지로 윈도우(창)를 한 칸씩 이동하며 패턴을 검사하지만, 모든 경우에 대해 일일이 문자 하나하나를 비교하지 않는다는 점이 큰 차이입니다. 대신 각 부분 문자열의 해시(hash) 값을 먼저 계산하여 비교하고, 해시 값이 일치할 때에만 실제 문자들을 하나씩 대조합니다. 이러한 방식 덕분에 텍스트의 각 부분 문자열마다 단 한 번의 비교만 수행하게 되어, 패턴 검색에 훨씬 효율적인 알고리즘이 됩니다.
시간 복잡도
- 전처리 시간(Preprocessing time): O(m)
- 평균 및 최선의 경우: O(m+n)
- 최악의 경우(Worst case): O(mn) — 해시 충돌이 빈번하게 발생할 때
알고리즘 동작 과정
rabinkarp_algo(text, pattern, prime)
입력 − 원본 텍스트와 검색할 패턴, 그리고 해시 위치 계산에 사용할 소수(prime number)
출력 − 패턴이 발견된 위치들
Start
pat_len := 패턴의 길이
str_len := 문자열의 길이
patHash := 0, strHash := 0, h := 1
maxChar := 문자 집합의 총 문자 수
패턴의 모든 문자 인덱스 i에 대해 반복:
h := (h*maxChar) mod prime
패턴의 모든 문자 인덱스 i에 대해 반복:
patHash := (maxChar*patHash + pattern[i]) mod prime
strHash := (maxChar*strHash + text[i]) mod prime
i := 0부터 (str_len - pat_len)까지 반복:
만약 patHash = strHash라면,
charIndex := 0부터 pat_len-1까지 반복:
만약 text[i+charIndex] ≠ pattern[charIndex]라면 break
만약 charIndex = pat_len이라면,
i 위치에서 패턴이 발견되었음을 출력
만약 i < (str_len - pat_len)이라면,
strHash := (maxChar*(strHash – text[i]*h)+text[i+patLen]) mod prime
만약 strHash < 0이라면,
strHash := strHash + prime
EndC 언어 구현 예제
다음은 라빈-카프 알고리즘을 C 언어로 구현한 전체 코드입니다.
#include<stdio.h>
#include<string.h>
int main (){
char txt[80], pat[80];
int q;
printf ("Enter the container string \n");
scanf ("%s", &txt);
printf ("Enter the pattern to be searched \n");
scanf ("%s", &pat);
int d = 256;
printf ("Enter a prime number \n");
scanf ("%d", &q);
int M = strlen (pat);
int N = strlen (txt);
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 + pat[i]) % q;
t = (d * t + txt[i]) % q;
}
for (i = 0; i <= N - M; i++){
if (p == t){
for (j = 0; j < M; j++){
if (txt[i + j] != pat[j])
break;
}
if (j == M)
printf ("Pattern found at index %d \n", i);
}
if (i < N - M){
t = (d * (t - txt[i] * h) + txt[i + M]) % q;
if (t < 0)
t = (t + q);
}
}
return 0;
}코드 핵심 포인트
- d = 256: 확장 아스키(ASCII) 문자 집합의 크기를 나타내며, 해시 계산의 밑(base)으로 사용됩니다.
- q: 해시 값의 범위를 제한하기 위한 큰 소수로, 사용자가 직접 입력합니다.
- 롤링 해시(Rolling Hash): 윈도우가 이동할 때 전체 해시를 다시 계산하지 않고, 앞 문자를 빼고 새 문자를 더하는 방식으로 O(1)에 해시 값을 갱신합니다.
- 음수 처리: 모듈러 연산 중 음수가 나올 수 있으므로, t < 0일 때 q를 더해 양수로 보정합니다.
실행 결과
Enter the container string tutorialspointisthebestprogrammingwebsite Enter the pattern to be searched p Enter a prime number 3 Pattern found at index 8 Pattern found at index 21
위 실행 결과에서 볼 수 있듯이, 입력된 텍스트에서 패턴 "p"가 등장하는 두 위치(인덱스 8과 21)가 정확히 출력됩니다. 이처럼 라빈-카프 알고리즘은 해시 값을 활용해 불필요한 문자 비교를 줄여주기 때문에, 긴 텍스트에서 여러 패턴을 검색해야 하는 상황에서 특히 유용하게 활용될 수 있습니다.