小编Pin*_*uck的帖子

我有兴趣实现Rabin-Karp算法来搜索维基上所述的子字符串:http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm.不是为了完成家庭作业,而是为了自身利益.我已经实现了Rabin-Karp算法(如下所示)并且它可以工作.但是,性能真的非常糟糕!我知道我的哈希函数是基本的.但是,似乎对strstr()的简单调用总是胜过我的函数rabin_karp().我可以理解为什么 - 哈希函数比简单的char-by-char比较每个循环做更多的工作.我在这里错过了什么？Rabin-Karp算法应该比调用strstr()更快吗？何时最好使用Rabin-Karp算法？因此,我的自身利益.我甚至实现了算法吗？

size_t hash(char* str, size_t i)
{
   size_t h = 0;
   size_t magic_exp = 1;
// if (str != NULL)
   {
      while (i-- != 0)
      {
         magic_exp *= 101;
         h += magic_exp + *str;
         ++str;
      }
   }

   return h;
}

char* rabin_karp(char* s, char* find)
{
   char* p = NULL;

   if (s != NULL && find != NULL)
   {
      size_t n = strlen(s);
      size_t m = strlen(find);

      if (n > m)
      {
         size_t hfind …