c++ - Rabin-Karp算法

我有兴趣实现Rabin-Karp算法来搜索子字符串，如Wiki:http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm所述。不是为了功课，而是为了个人利益。我已经实现了Rabin-Karp算法(如下所示)，并且可以正常工作。但是，性能真的非常糟糕!!!我了解我的哈希函数是基本的。但是，似乎简单地调用strstr()总是会胜过我的函数rabin_karp()。我能理解为什么-哈希函数比简单的逐个字符比较每个循环要完成更多的工作。我在这里想念什么？ 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 = hash(find, m);

         char* end = s + (n - m + 1);
         for (char* i = s; i < end; ++i)
         {
            size_t hs = hash(i, m);
            if (hs == hfind)
            {
               if (strncmp(i, find, m) == 0)
               {
                  p = i;
                  break;
               }
            }
         }
      }
   }

   return p;
}

最佳答案

您尚未正确实现哈希。 Rabin-Karp的关键是随着潜在匹配沿着要搜索的字符串移动而逐步更新哈希。正如您已经确定的那样，如果您为每个潜在的匹配位置重新计算整个哈希，事情将会真的很慢。

对于除第一个比较之外的所有情况，您的哈希函数都应采用一个现有哈希，一个新字符和一个旧字符，并返回更新后的哈希。

关于c++ - Rabin-Karp算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10256913/