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はテンプレートの長さです。

一般規則：小数でなければならず、基数は使用するのに便利でなければなりません。 私はのようなペアを信じる：^ 64

2のためにOKになり、

（プライム、基数）

31、2^64

37、2^64

57君は。

ハッシュの衝突を最小限にする実装では、複数のペアが使用されます。

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