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，2^64

37，2^64

57，2^64

將是行您。

在使散列衝突最小化的一些實現中，使用多於一對的實現。

Answer 2

拉賓KARP字符串匹配算法
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