Proper implementation of the Boyer Moore algorithm

Question

I tried to use several implementations, but all of them had errors.
A search in SO gave me http://www-igm.univ-mlv.fr/~lecroq/string/node14.html - it looks nice, but this implementation gave me the wrong results - sometimes it could not find a string. <sh> I spent a couple of hours to find the error.

The following line looks fine:

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

but y char * and char are signed ! This means that y [i + j] can be negative (which happens in one of my tests).

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

Answer 1

char - .

, char , unsigned char ( , C - unsigned char).

Answer 2

Wikipedia?

PDF, ?

Answer 3

++ 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;
}