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