Использование алгоритма Бойера-Мура-Хорспула в Java с примером решения задачи с LeetCode

Поделиться
  • 25 июля

Алгоритм Хорспула используется для нахождения подстроки в строке. Например, у нас есть строка «The game is over» и подстрока «over». Алгоритм Хорспула вернет значение первого вхождения подстроки «over» в строку «The game is over», а именно 12. 

Фактически, данный алгоритм является упрощенным алгоритмом Бойера-Мура, который, считается работает лучше, чем стандартный алгоритм на случайных текстах, но в худшем случае его скорость равна |needle| * |haystack| вместо 3 х |haystack|. 

Тем не менее, для восприятия, на мой взгляд, он гораздо проще.

Итак, погнали.

Условие задачи с leetcode: https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/description/

Как работает алгоритм?

Строка и подстрока совмещаются по первому символу, и начинаются сравниваться от последнего символа к первому.

Для примера возьмем строку: «aabcdadbc» и подстроку «adb»

Совмещаются строки следующим образом (слева направо):

Читать далее