Поиск подстроки в строке. Алгоритм Бойера-Мура. Алгоритм Кнутта-Морриса-Пратта

Алгоритм Кнутта-Морриса-Пратта
Реализация: https://gist.github.com/kehtolaulu/204b6b24089537766fe8668590931ee0
Сложность: O(n)

Алгоритм Бойера-Мура
Реализация: https://gist.github.com/kehtolaulu/35dc48dfd8a51064282c9cc27b387fd5
Один из способов реализации алгоритма Бойера-Мура - таблица смещения D. Для этого используется таблица ASCII, которая содержит 256 символов. Мы заводим массив размером 256.
Изначально все элементы массива D - все двести пятьдесят шесть элементов - мы инициализируем числом равным длине образа, и после этого начинаем изменять значения в этом одномерном массиве следующим образом:
каждой букве (в таблице кодов ASCII) соответствует некоторое значение.

Таким образом массиве D мы можем в ячейки, которые соответствуют кодам символов записывать значение таблицы смещения D.
Например, у нас есть 'д', значение этого символа 228, и вот в эту ячейку мы записываем значение 5.
В 'a' значение таблицы смещения равно 4, а значение таблицы кодов ASCII 224.
Вот в 224-ую ячейку массива D мы записываем 4.

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

Сложность:
В наихудшем случае строка содержит n одинаковых символов. Образ начинается с какого-то другого символа и потом идут эти же самые символы, которые представлены в строке. Всего символов в образе в m. В этом случае временная сложность алгоритма будет равна O( n * m ).
В наилучшем случае строка содержит n каких-то символов, а образ содержит m других символов.
В этом случае временная сложность алгоритма будет равна O( m / n ).
В общем же случае временная сложность алгоритма будет O(m / |E|), где E это множество, которое включает себя все символы, которые могут быть представлены в строке и в образе. Это могут быть символ русского алфавита, латиницы, цифры, знаки препинания и другие символы, которые мы видели в таблице ASCII.

Видео Поиск подстроки в строке. Алгоритм Бойера-Мура. Алгоритм Кнутта-Морриса-Пратта канала Hei maailma!