Как работает алгоритм Бойера-Мура?
Поясните, пожалуйста, понятным языком (по возможности, подробно), как работает этот алгоритм. Очень хотелось бы разобраться
Люди старались, переводили, добавляли
1й раз встречаю в вики русский вариант полнее (и понятнее) английского. А вам всё одно непонятно
Просто подумай, как бы ты реализовал алгоритм поиска слова в строке. Самый простой алгоритм, который придёт тебе в голову - это и будет алгоритм того Чувака.
Процедура алгоритма очень простая. Сначала строится таблица смещений для каждого символа. Затем исходная строка и шаблон совмещаются по началу, сравнение ведется по последнему символу. Если последние символы совпадают, то сравнение идет по предпоследнему символу и так далее. Если же символы не совпали, то шаблон смещается вправо, на число позиций взятое из таблицы смещений для символа из исходной строки, и тогда снова сравниваются последние символы исходной строки и шаблона. И так далее, пока не шаблон полностью не совпадет с подстрокой исходной строки, или не будет достигнут конец строки.