Rabin-Karp算法

Question

我对实现Rabin-Karp算法以查找子字符串感到兴趣，如维基所述: 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;
}

- PinkDuck

---

我敢打赌你可以反转rabin_karp中的循环，然后重构hash使其成为O(1)。 - Alexander

Answer 1

你没有正确地实现哈希。Rabin-Karp算法的关键是在潜在匹配项沿着要搜索的字符串移动时增量更新哈希。正如你所确定的那样，如果你对每个潜在匹配位置重新计算整个哈希，速度会非常慢。

除了第一次比较之外，对于每种情况，你的哈希函数应该采用一个现有哈希、一个新字符和一个旧字符，并返回一个更新后的哈希值。

- Sean Reilly

---

它还在您在问题中引用的Wiki页面中指出：滚动哈希。 - Pupsik

Answer 2

Rabin-Karp是一种滚动哈希算法——其思想是能够将子字符串向左或向右移动一个位置，并能够通过常数次操作重新计算哈希。如果您已经实现它，那么搜索的复杂度为O(N * L)，其中N是大字符串的长度，L是正在搜索的字符串的长度。这是最朴素方法的复杂度，实际上在我看来有点慢。

为了改进您的算法，请预先计算magic_exp的指数，并使用它们来'滚动'您的哈希值——基本上就像多项式一样，您需要减去最高次乘以magic_exp并将符号的哈希添加到右侧（用于将哈希向右移动）。

希望这可以帮助您。

- Ivaylo Strandjev

Answer 3

strstr使用KMP算法，该算法也是线性的。这意味着两种算法的复杂度大致相同。从那时起，常数是重要因素。特别是在您具有许多冲突的坏哈希函数的情况下，KMP将更快。

编辑：还有一件事。对于Rabin Karp算法来说，预先计算所有前缀的哈希码非常重要。现在，您没有实现正确的Rabin Karp，因为调用您的函数将是线性的，而不是常数的复杂度。（顺便说一句，这意味着维基百科不是学习Rabin Karp的很好的来源）。

- Boris Strandjev