Правильная реализация алгоритма Бойера Мура

Question

Я пытался использовать несколько реализаций, но во всех них были ошибки.
Поиск в SO дал мне http://www -igm.univ-mlv.fr / ~ lecroq / string / node14.html - выглядит хорошо, но эта реализация дала мне неправильные результаты - иногда она не находит строку.
Я потратил пару часов, чтобы найти ошибку.

Следующая строка выглядит хорошо:

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

но y - это символ *, а символ подписан !Это означает, что y [i + j] может быть отрицательным (что происходит в одном из моих тестов).

Мой вопрос: где найти правильную реализацию алгоритма Бойера Мура?

Answer 1

char не является окончательно подписанным или без знака - оно не указано и оставлено на усмотрение реализации.

Если алгоритм зависит от неподписанного символа, то он должен явно привести входные указатели к unsigned char (именно так определяются функции обработки строк стандартной библиотеки C - все сравнения выполняются с обработкой символов в строке как unsigned char).

Answer 2

Вы пробовали Википедия ?

Или PDF, написанный изобретателями алгоритма ?

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