Алгоритм Хорспула используется для нахождения подстроки в строке. Например, у нас есть строка «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»
Совмещаются строки следующим образом (слева направо):
