반응형
문자열 탐색은 코딩 테스트에서 꽤 자주 출제되는 유형입니다. 오늘은 지난 포스팅에 이어서 문자열 탐색에서 유명한 라빈 카프 알고리즘 (Rabin-Karp Algorithm) 에 대해 알아보겠습니다.
라빈 카프 알고리즘의 개념부터 동작 원리, 예제, 장단점, 그리고 다양한 프로그래밍 언어로 구현된 예제 코드까지 다루겠습니다. 초보자도 이해하기 쉽도록 하나하나 상세히 설명하겠습니다. 😊
1. 라빈 카프 알고리즘의 개념
라빈 카프 알고리즘은 텍스트 내에서 특정 패턴을 찾기 위해 해시 값을 사용하는 알고리즘입니다.
- 텍스트의 부분 문자열(substring)과 패턴의 해시 값을 비교하여 패턴이 존재하는 위치를 찾습니다.
- 단순 비교 알고리즘(Brute Force)보다 효율적이며, 특히 여러 패턴을 검색할 때 유용합니다.
반응형
2. 동작 원리
(1) 핵심 아이디어
라빈 카프 알고리즘은 패턴과 텍스트의 서브스트링을 하나씩 비교하는 대신, 해시 값을 비교하여 매칭을 수행합니다.
- 해시 값이 같으면 실제 문자열 비교를 수행하여 패턴의 위치를 확인합니다.
- 슬라이딩 윈도우(sliding window) 방식으로 텍스트의 서브스트링 해시 값을 효율적으로 갱신합니다.
(2) 단계별 동작 과정
- 패턴과 첫 번째 서브스트링의 해시 값 계산
- 패턴의 해시 값을 계산합니다.
- 텍스트의 첫 번째 서브스트링의 해시 값을 계산합니다.
- 해시 값 비교
- 패턴과 텍스트 서브스트링의 해시 값이 같으면 실제 문자열을 비교합니다.
- 해시 값이 다르면 다음 서브스트링으로 넘어갑니다.
- 슬라이딩 윈도우로 다음 해시 값 갱신
- 이전 해시 값을 활용하여 새로운 서브스트링의 해시 값을 효율적으로 계산합니다.
(3) 구체적인 동작 예시
0) 입력
- 텍스트: ABCDABC
- 패턴: ABC
- 해시 함수: 롤링 해시 (base = 31, mod = 101)
1) 해시 함수 정의
여기서:
- base: 임의의 고정된 값 (예: 31).
- q: 큰 소수(충돌 방지).
2) 초기 해시 계산
- 패턴 ABC와 텍스트 첫 서브스트링 ABC의 해시 값을 계산합니다.
3) 슬라이딩 윈도우 갱신
- 두 번째 서브스트링 BCD의 해시 값 계산:
4) 결과 요약 (표로 정리)
윈도우 위치서브스트링해시 값패턴 해시 값매칭 결과
| 윈도우 위치 | 서브스트링 | 해시 값 | 패턴 해시 값 | 매칭 결과 |
| 0 | ABC | 41 | 41 | 매칭 성공 |
| 1 | BCD | 59 | 41 | 매칭 실패 |
| 2 | CDA | 97 | 41 | 매칭 실패 |
| 3 | DAB | 79 | 41 | 매칭 실패 |
| 4 | ABC | 41 | 41 | 매칭 성공 |
3. 시간 복잡도
- 평균 시간 복잡도: (해시 충돌이 적을 경우).
- 최악 시간 복잡도: (모든 해시 값이 충돌할 경우).
4. 장단점
장점
- 여러 패턴 탐색에 유리: 다수의 패턴을 한 번에 처리 가능.
- 효율적인 서브스트링 탐색: 슬라이딩 윈도우로 해시 값을 갱신하여 계산량 감소.
단점
- 해시 충돌 가능성: 다른 문자열이 같은 해시 값을 가질 수 있음.
- 긴 패턴에 비효율적: 해시 계산의 비용이 증가.
5. 예시 코드
C 언어
#include <stdio.h>
#include <string.h>
#define BASE 31
#define MOD 101
void search(char* pattern, char* text) {
int m = strlen(pattern);
int n = strlen(text);
int p_hash = 0;
int t_hash = 0;
int h = 1;
for (int i = 0; i < m - 1; i++) {
h = (h * BASE) % MOD;
}
for (int i = 0; i < m; i++) {
p_hash = (BASE * p_hash + pattern[i]) % MOD;
t_hash = (BASE * t_hash + text[i]) % MOD;
}
for (int i = 0; i <= n - m; i++) {
if (p_hash == t_hash) {
int j;
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) {
t_hash = (BASE * (t_hash - text[i] * h) + text[i + m]) % MOD;
if (t_hash < 0) t_hash += MOD;
}
}
}
int main() {
char text[] = "ABCDABC";
char pattern[] = "ABC";
search(pattern, text);
return 0;
}Java
public class RabinKarp {
private static final int BASE = 31;
private static final int MOD = 101;
public static void search(String text, String pattern) {
int m = pattern.length();
int n = text.length();
int pHash = 0, tHash = 0, h = 1;
for (int i = 0; i < m - 1; i++) {
h = (h * BASE) % MOD;
}
for (int i = 0; i < m; i++) {
pHash = (BASE * pHash + pattern.charAt(i)) % MOD;
tHash = (BASE * tHash + text.charAt(i)) % MOD;
}
for (int i = 0; i <= n - m; i++) {
if (pHash == tHash) {
if (text.substring(i, i + m).equals(pattern)) {
System.out.println("Pattern found at index " + i);
}
}
if (i < n - m) {
tHash = (BASE * (tHash - text.charAt(i) * h) + text.charAt(i + m)) % MOD;
if (tHash < 0) tHash += MOD;
}
}
}
public static void main(String[] args) {
String text = "ABCDABC";
String pattern = "ABC";
search(text, pattern);
}
}Python
def rabin_karp(text, pattern, base=31, mod=101):
m, n = len(pattern), len(text)
p_hash = 0
t_hash = 0
h = 1
for i in range(m - 1):
h = (h * base) % mod
for i in range(m):
p_hash = (base * p_hash + ord(pattern[i])) % mod
t_hash = (base * t_hash + ord(text[i])) % mod
for i in range(n - m + 1):
if p_hash == t_hash:
if text[i:i + m] == pattern:
print(f"Pattern found at index {i}")
if i < n - m:
t_hash = (base * (t_hash - ord(text[i]) * h) + ord(text[i + m])) % mod
if t_hash < 0:
t_hash += mod
text = "ABCDABC"
pattern = "ABC"
rabin_karp(text, pattern)
반응형
댓글