正确实施博耶Moore算法 [英] Correct implementation of Boyer Moore algorithm

问题描述

我试图用几种实现，但他们有错误。
搜索在SO给我 HTTP：//www-igm.univ-mlv .FR /〜lecroq /串/ node14.html - 看起来不错，但这种实现给了我错误的结果 - 有时它没有找到一个字符串
。 我花了几个小时来寻找错误的。

I tried to use several implementations, but all of them had bugs.
Search at SO gave me http://www-igm.univ-mlv.fr/~lecroq/string/node14.html - looks nice, but this implementation gave me wrong results - sometimes it doesn't found a string.
I spent couple hours to find the bug.

下面这行看起来不错：

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

不过的是的为char *和char是签署！这意味着，值Y [i + j]的可能是负的（在我的测试中，会有什么结果）。

but y is char * and char is signed! It means that y[i + j] could be negative (what happens in one of my tests).

我的问题是：在哪里可以找到正确实施博耶Moore算法

My question is: Where to find correct implementation of Boyer Moore algorithm?

推荐答案

字符未明确签署的或的无符号 - 这是不确定的，并留给实现来定义。

char isn't definitively signed or unsigned - it's unspecified, and left up to the implementation to define.

如果该算法依赖于焦炭是无符号的，那么就应该明确地转换输入指针无符号的字符（这是怎样的C标准库字符串处理函数定义为工作 - 所有的比较都是做处理字符串中的字符作为无符号的字符）

If the algorithm depends on char being unsigned, then it should explicitly cast the input pointers to unsigned char (which is how the C standard library string handling functions are defined to work - all comparisons are done treating the characters in the string as unsigned char).

这篇关于正确实施博耶Moore算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！