Boyer Moore算法的正确实现

Question

我尝试使用多种实现，但所有实现都存在缺陷。
在SO上搜索得到了http://www-igm.univ-mlv.fr/~lecroq/string/node14.html - 看起来很不错，但是这个实现给了我错误的结果 - 有时它无法找到一个字符串。
我花了几个小时的时间来查找错误。

以下代码行看起来不错：

j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);

但是y是char*类型，而char类型是有符号的！这意味着y[i+j]可能是负数（在我的测试中发生了这种情况）。

我的问题是：在哪里可以找到正确的Boyer Moore算法实现？

- Dmitriy

---

FYI，字符串算法领域的权威参考书是Dan Gusfield的《字符串、树和序列算法》。 - San Jacinto

@San Jacinto：你应该把你的评论写成答案——这本书真的很好！ - Dmitriy

Answer 1

你试过维基百科吗？

或者是该算法的发明者编写的PDF文档？

- In silico

Answer 2

char类型不确定是有符号还是无符号的 - 它是未指定的，具体定义由实现决定。

如果算法依赖于char是无符号的，则应将输入指针显式转换为unsigned char（这是C标准库字符串处理函数的定义方式 - 所有比较都将字符视为unsigned char进行处理）。

- caf

Answer 3

从C++17开始，这已经内置于STL中。只需使用std::boyer_moore_searcher即可。例如：

#include <algorithm>
#include <string>
#include <functional>

int main()
{
    std::string haystack = "The quick brown fox jumped over the lazy dog";
    std::string needle = "brown";
    const auto s = std::boyer_moore_searcher<std::string::iterator>(needle.begin(), needle.end());
    const auto it = std::search(haystack.begin(), haystack.end(), s);
    return 0;
}

- TamaMcGlinn