Rabin-Karp 문자열 검색 알고리즘

Question

내 previous question은 일반 문자열 검색 알고리즘과 관련이 있습니다. 가 나는 라빈 - 카프 알고리즘을 연구하고 있는데이 같은 함수 템플릿이 있습니다

RabinKarpMatch(char *Text, char *Search_phrase,int radix,int prime) 

내가 기수와 소수의 값이 SEARCH_PHRASE 및 텍스트에 따라 변경하는 방법을 알고 싶어? 아니면 모든 경우에 임의의 값을 부여해야합니까?

Answer 1

Rabin-Karp 알고리즘에서 기수 및 소수는 텍스트 처리 중에 변경되지 않습니다. 그러나 좋은 기수와 소수를 선택하는 것은 매우 중요합니다. 텍스트의 모든 부분 문자열이 템플릿 해시 코드와 동일한 해시 코드를 가질 때 최악의 경우 (거의 불가능) 알고리즘은 O (nm) 시간에 작동합니다. 여기서 n은 텍스트 길이이고 m은 템플릿 길이입니다.

일반 규칙 : 프라임 - 작아야하며 기수 - 사용하기 편리해야합니다.

(프라임 기수)

31^64

37 2^64

57 (2)는, 2^64

가 OK 일 것이다 내가 좋아 쌍 판단 당신.

해시 충돌을 최소화하는 일부 구현에서는 두 개 이상의 쌍이 사용됩니다.

Answer 2

라빈 카프 STRING 매칭 알고리즘
CODE : 여기

#include <stdio.h> 
#include <conio.h> 
#include <string.h> 
#include <math.h> 
#define d 10 
void RabinKarpStringMatch(char*, char*, int); 
void main() 
{ 
    char *Text, *Pattern; 
    int Number = 11; //Prime Number 
    clrscr(); 
    printf("\nEnter Text String : "); 
    gets(Text); 
    printf("\nEnter Pattern String : "); 
    gets(Pattern); 

    RabinKarpStringMatch(Text, Pattern, Number); 
    getch(); 
} 

void RabinKarpStringMatch(char* Text, char* Pattern, int Number) 
{ 
    int M, N, h, P = 0, T = 0, TempT, TempP; 
    int i, j; 
    M = strlen(Pattern); 
    N = strlen(Text); 
    h = (int)pow(d, M - 1) % Number; 
    for (i = 0; i < M; i++) { 
     P = ((d * P) + ((int)Pattern[i])) % Number; 
     TempT = ((d * T) + ((int)Text[i])); 
     T = TempT % Number; 
    } 
    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("\nPattern Found at Position: %d", i + 1); 
     } 
     TempT = ((d * (T - Text[i] * h)) + ((int)Text[i + M])); 
     T = TempT % Number; 
     if (T < 0) 
      T = T + Number; 
    } 
} 

OUTPUT FOR THE CODE