C++ 奇怪的结果 - 蛮力比 Rabin-Karp 更快......？

Question

目前正在为一个 uni 模块开发一个字符串搜索程序，我已经成功地实现了这些算法，至少达到了他们始终如一地找到字符串的程度。我实现了 Boyer Moore 和 Rabin Karp。当我的一位同学遇到这个确切的问题时，我也投入了蛮力，并意识到我遇到了同样的问题 - 蛮力比单词列表中的 Rabin-Karp 更快。

Rabin-Karp 似乎花费了最多的时间来执行滚动散列，起初我很好奇我是否只是有很多碰撞，但我设法将碰撞降低到 3 个巨大的质数数字。由于素数的大小，我假设这增加了一点时间，但很明显滚动哈希导致了问题。

这是滚动哈希部分：

//hashes don't match, rehash using rolling hash to move on to next string section
  if (counter < (stringLength - patternLength)) { 

            stringHash = (MAXCHAR *(stringHash - stringFile[counter] * hash) + stringFile[counter + patternLength]) % prime;


            if (stringHash < 0) {

                stringHash += prime;    //when hash value is negative, make it positive
            }

        }

        if (!found) {

            counter++; 
        }

我想尝试搜索一个巨大的文本文件，所以我使用了 rockyou 词表，Boyer Moore 对它非常满意，而 Rabin-Karp 很快就完成了。 Brute Force 花费的时间不到 Rabin-Karp 的一半，但对我来说这没有意义？

我是不是误解了应该如何应用这些算法，还是我正在使用的滚动哈希过程有问题？

Answer 1

暴力字符串搜索是 Rabin-Karp 的特例，具有常量哈希函数（因此每个滚动哈希匹配）。

两种算法的最坏情况复杂度相同，"average case" 的大多数定义的平均情况复杂度也是如此。

在这些情况下，由于计算和检查良好哈希的开销，Rabin-Karp 将花费更长的时间。

与 Rabin-Karp 相比，蛮力的问题在于现实生活中有时会发生糟糕的情况。例如，如果您正在搜索路径名，那么您的模式可能有一个与文件中的许多或大部分路径名和部分路径名相同的长前缀，这将使暴力破解需要很长时间时间.

使用 Rabin-Karp，坏情况在现实生活中发生的可能性很小。它们实际上只在 "adversarial" 条件下发生，在这种情况下，文件和模式是有目的地构建的，需要很长时间，并且对您使用的哈希函数有特定的了解。

即便如此...Rabin-Karp 并不是用于单一模式搜索的出色算法。当您同时搜索多个字符串时，它会变得更加有用，您可以在潜在匹配的字典中查找滚动哈希。

C++ 奇怪的结果 - 蛮力比 Rabin-Karp 更快......？

C++ strange results - brute force is quicker than Rabin-Karp...?

algorithm

brute-force

string-search

rabin-karp