c++ - 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 是signed!这意味着 y[i + j] 可能为负(在我的一个测试中发生了什么)。

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

Answer 1

char 未明确签名或未签名 - 它未指定，由实现来定义。

如果算法依赖于 char 是无符号的，那么它应该显式地将输入指针转换为 unsigned char(这是 C 标准库字符串处理函数定义的工作方式 - 所有比较都已完成将字符串中的字符视为 unsigned char)。