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

Алгоритм Кнутта-Морриса-Пратта Реализация:
Сложность: O(n) Алгоритм Бойера-Мура-Хорспула (?) Реализация:
Один из способов реализации алгоритма Бойера-Мура - таблица смещения 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.