Поиск подстроки в строке. Алгоритм Бойера-Мура. Алгоритм Кнутта-Морриса-Пратта
Vložit
- čas přidán 18. 05. 2018
- Алгоритм Кнутта-Морриса-Пратта
Реализация: gist.github.com/kehtolaulu/20...
Сложность: O(n)
Алгоритм Бойера-Мура-Хорспула (?)
Реализация: gist.github.com/kehtolaulu/35...
Один из способов реализации алгоритма Бойера-Мура - таблица смещения 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.
Какое видео-объяснение ещё хотим? Пишите в комменты!
Очень хорошее объяснение
Любое другое из задач средней сложности,
переиспользуемое, которое часто может пригодится, или просто неочевидное, удобное
- на селедку с клумбой и эффектом 2х уровней.
КТО СМОТРИТ В 2020, ЛАЙК!
коронавирус задолбал)
Спасибо за помощь с курсовой ;)
хорошее видео, спасибо.
декабрь 2020
2021 так-то)))
прекрасний голос и обьяснение) большое спасибо
Спасибо, наглядно!
Жаль, что таких видео мало.
очень понятно, спасибо! отдельная благодарность за код на java
Респект))) перед сессией самое то смотреть)
Продолжайте!!
все понятно спасибо
Топ. Все быстро и понятно
хочу такую же умную жену
А ничего, что это алгоритм Бойера-Мура-Хорспула, а не Бойера-Мура?
спасибо, я не знала!
Так он наверное и работает по другому тогда?? Держите в курсе, Алёна, очень важная информация)
Да пусть хранит тебя джопс
ничего не понятно что нашли ? а что искали?? но было интересно =)
них*я не понял, но ОЧЕНЬ интересно !!!
в названии видео один алгоритм, а реализуют другой
как такое на си написать? у кого-нибудь есть код?
Вот накидал велосипед с квадратными колёсами
#include
#include
#include
char* strrevchr(char* line, int len , const char chr);
char* _strstr(char* haystack,char* needle);
int main(int a,char** b){
char* res=_strstr("Где ваши Данные?","Данные");
puts(res);
return 0;
}
char* _strstr(char* haystack,char* needle){
int len = strlen(needle); //длина запроса /6
char* end_adress = len + needle; //адрес конца
char* table =(char*) malloc(len); //table
//-- Составляем таблицу --
for (int i=1; i
По алгоритму Бойера-Мура
ucode - top
Посмотрите лучше что-нибудь другое на эту тему.
Сбивчивое, сумбурное и сухое объяснение, упускающее из виду важные для понимания моменты. Авторка будто перед экзаменационной комиссией докладывается, а не пытается что-то доходчиво донести. Ужасно.
авторка
Лучший видеоролик. Автору респект. Остальные видео от студентов дегенератов, у которых в голове такая каша, что можно роту солдат накормить.