이 문제에서는 두 개의 문자열 텍스트와 패턴이 제공됩니다. 우리의 임무는 패턴 검색을 위한 Rabin-Karp 알고리즘을 위한 프로그램을 만드는 것입니다. 이 프로그램은 텍스트 문자열에서 패턴의 모든 항목을 찾을 것입니다.
여기서 우리는 텍스트에서 패턴의 모든 발생을 찾아야 합니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력
text = “xyztrwqxyzfg” pattern = “xyz”
출력
Found at index 0 Found at index 7
여기서는 Rabin-Karp 알고리즘을 사용하여 문제를 해결하는 방법에 대해 설명합니다. 이 알고리즘에서는 문자열에서 패턴 크기의 창을 가져와 하나씩 밀어 패턴의 해시 값과 일치시킵니다. 그리고 해시 값이 일치하면 패턴의 개별 문자가 문자열과 일치하는지 확인합니다.
Rabin-Karp의 경우 텍스트 및 패턴의 해시 값이 중요합니다. 패턴 생성을 위해 모든 문자의 숫자 값을 추가합니다
문자열과 해시의 문자는 값을 작게 만들기 위해 소수로 나누어 고려됩니다.
패턴 검색을 위한 Rabin-Karp 알고리즘 프로그램
//패턴 검색을 위한 Rabin-Karp 알고리즘 프로그램
예시
#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;
} 출력
패턴은 다음 색인의 텍스트에서 찾을 수 있습니다. -
Pattern found at index 0 Pattern found at index 7