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

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

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

После совмещения строк, начинает происходить сравнение справа налево, если символ совпадает, то сравнивается предыдущий, пока не закончится подстрока.

В нашем случае сравнение начинается с символа «b», в строке и подстроке этот символ совпадает, поэтому переходим к предыдущему: строка — «a», подстрока — «d», т.е. они не равны, а поэтому мы можем сместить нашу подстроку на некоторое количество символов, которое мы возьмем из таблицы смещений.

Таблица смещений — это штука, которая строится для подстроки, где каждому символу присваивается свой номер максимально возможного смещения, начиная с конца и исключая последний символ. Для всех остальных символов, которых нет в подстроке, и для последнего символа подстроки в качестве номера присваивается размер подстроки.

Например, для подстроки «over» таблица смещений будет выглядеть следующим образом:

Если элементы повторяются, например aababd, то смещение будет присвоено по последнему совпадающему символу:

Можно упросить до:

Для нашего примера таблица смещений будет следующая:

В строке, значение, которое не совпало с искомым — это «a», для которого смещение равно 2, т.е. мы можем сместить поиск в нашей строке на 2 элемента:

Теперь начинаем снова сравнивать справа налево: «d» и «b» не равны друг другу, поэтому идем в таблицу смещений и находим значение для символа из строки «d», это 1. Смещаем нашу подстроку на 1 вправо для дальнейшего сравнения.

Снова сравниваем последние символы «a» и «b», они не равны, находим смещение для «a» из таблицы смещений — 2, смещаем подстроку на 2 символа вправо:

Начинаем снова сравнение: b = b, d = d, a = a. Видим, что подстрока полностью совпала со строкой, и возвращаем «5» — индекс символа «a», который является первым символом совпадения строки с подстрокой.

Теперь реализуем этот код на Java:

public static int strStr(String haystack, String needle) {      int haystackLen = haystack.length();      int needleLen = needle.length();      // создаем таблицу смещений для символов искомого текста      Map<Character, Integer> offsetTable = new HashMap<>();      for (int i = 0; i < needleLen - 1; i++) {          offsetTable.put(needle.charAt(i), needleLen - i - 1);      }      int shift = 0; // смещение от начала строки      while (shift <= haystackLen - needleLen) {          int j = needleLen - 1;          // ищем с конца подстроки к началу          while (j >= 0 && needle.charAt(j) == haystack.charAt(shift + j)) {              j--;          }          // если подстрока найдена, возвращаем значение смещения          if (j < 0) {              return shift;          } else {              // Рассчитываем сдвиг на основе измененной эвристики стоп-символа              shift += Math.max(1, offsetTable.getOrDefault(haystack.charAt(shift + j), needleLen) - 1);          }      }      // если подстрока не найдена      return -1;  }

В целом прокомментировала каждый шаг в самом коде, но хочется обратить внимание на строку:

shift += Math.max(1, offsetTable.getOrDefault(haystack.charAt(shift + j), needleLen) — 1); и разобрать ее подробнее.

haystack.charAt(shift + j) — находим, какой символ находится в строке с учетом сдвига. На первом шаге нашего примера мы так нашли в строке символ «a» (символ первого несовпадения),  вот тут:

Смотрим дальше: offsetTable.getOrDefault(haystack.charAt(shift + j), needleLen) — 1 — т.к. в нашу таблицу мы поместили только сдвиги для символов из подстроки, то для всех остальных мы будем брать значение «needleLen», т.е. длину подстроки.

Затем мы уменьшаем наш сдвиг на единицу, т.к. выше идет сравнение needle.charAt(j) == haystack.charAt(shift + j), где j — это длина подстроки минус 1. Если не уменьшить сдвиг (shift) на 1, то сравнивать будем некорректные символы.

В конце мы берем либо значение максимально возможно сдвига, либо 1, так как максимально возможный сдвиг может стать равным 0 (можете попробовать прогнать пример, где строка «abc» и подстрока «c») и получаем: 

Math.max(1, offsetTable.getOrDefault(haystack.charAt(shift + j), needleLen) — 1);

Короче, вот такая штука, алгоритм Бойера-Мура-Хорспула. 

В худшем случае она, конечно, даст квадратичную временную сложность (точнее O(n * m)), но на практике из-за таблицы смещений работает гораздо эффективнее.

Хотя на leetCode алгоритм дал тот же 1ms Runtime, что и обычный перебор (хех):

public static int strStr(String haystack, String needle) {      if (haystack.length() < needle.length()) {          return -1;      }      for (int i = 0; i <= haystack.length() - needle.length(); i++) {          int j = 0;          while (haystack.charAt(i + j) == needle.charAt(j)) {              j++;              if (j == needle.length()) {                  return i;              }          }      }      return -1;  }

Но при тестах на длинные тексты, конечно, Хорспул победил.