正确实现Boyer Moore算法 [英] Correct implementation of Boyer Moore algorithm

问题描述

我尝试使用多种实现，但是所有这些实现都有错误。

在SO上搜索给我 http://www-igm.univ-mlv.fr/~lecroq/string/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);

但 y 强>！这意味着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).

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

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

推荐答案

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

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

如果算法依赖于char是无符号的，那么它应该显式地将输入指针转换为 unsigned char 库字符串处理函数被定义为工作 - 所有的比较都是通过处理字符串中的字符为 unsigned char ）。

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).

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