Это видео недоступно.
Сожалеем об этом.
Алгоритм Бойера-Мура-Хорспула
HTML-код
- Опубликовано: 12 авг 2024
- Понятно и доходчиво об алгоритме поиска в строке - алгоритме Бойера-Мура-Хорспула. Данный алгоритм эффективно решает задачу поиска слова или фразы в тексте. Алгоритм состоит из двух этапов:
1. Формирование таблицы смещения - 03:27
2. Непосредственно поиск образа в строке - 10:32
Кроме этого, в видео представлены:
- оригинальный подход к реализации алгоритма - 11:35
- анализ временной сложности алгоритма - 13:59
Спасибо большое! Самое ясное объяснение данного алгоритма)
Пожалуйста!
Большое спасибо!!! Просто, наглядно и понятно! Ваше видео очень помогло, наконец-то написала нормальный рабочий алгоритм поиска))
Пожалуйста! Ставьте лайк, подписывайтесь на канал )
Роман, спасибо вам за такое понятное объяснение, благодаря вашим видео я наконец разобрался с такими алг как этот и КМП
Пожалуйста.
Крутое видео! А то читаешь и ничего не понимаешь))
Вы отлично объясняете. Спасибо!
Спасибо за лестную оценку.
Суупер! Спасибо😊 очень понятно и наглядно)
Пожалуйста
Спасибо большое, помогло
Пожалуйста!
Спасибо! Очень понятно!
Пожалуйста!
Супер! Спасибо!
Пожалуйста!
большое спасибо! теперь все точно уложилось в голове))
Пожалуйста.
Можно вопрос, а не нужно удалять пробелы, прежде чем применять алгоритм? То есть возможен вариант, когда сдвиг слова по таблице смещений поставит его так, что последний символ образа будет сравниваться с пробелом - что в таком случае?
Прекрасный вопрос! Для ответа на него рассмотрим программную реализацию. При формировании массива d я использовал таблицу ASCII (11:50). Если взглянуть на нее, то можно увидеть, что пробел имеет код 32. То есть для ЭВМ пробел - это такой же символ как и любая буква, цифра, знак препинания (которые, естественно, имеют свои коды). Так что пробелы предварительно удалять не нужно. Более того, образ может быть не отдельным словом, а фразой и, конечно, будет содержать пробелы, которые тоже удалять не нужно.
выглядит как какая-то магия)))
Это она и есть
Подскажите, алгоритм
sha 256 тоже на сдвиге работает или другие алгоритмы использует?
Нужно понять сам принцып работы hashlib.
Я не в курсе, если честно
@@romantsarev1145 ruclips.net/video/mbekM2ErHfM/видео.html
На сколько нужно сдвигать индекс при нахождении элемента, если нужно найти несколько вхождений?
Все зависит от Вашей постановки задачи. Если Вы считаете, что в строку "аааа" образ "аа" входит три раза, тогда на один символ. А, если входит два раза, тогда начинайте с символа, который стоит сразу за совпавшей частью строки и образа. В целом, алгоритм ищет первое совпадение образа и строки, остальное на усмотрение программиста.
@@romantsarev1145 я увеличивал индекс і (тот, который идёт по строке) на значение из таблицы сдвигов последнего совпавшего символа. Вроде работает нормально.
Спасибо, но кое что очень странно. В первом примере ты считаешь смещение относительно символов с строке, а во втором примере относительно образа
Если при сравнении последнего символа образа и символа строки произошло несовпадение, то определяем сдвиг по символу строки (6:59);
если же несовпадение произошло после того, как совпал ряд символов строки и образа, то сдвиг будет равен d, соответствующий последнему символу образа (9:17).
Roman Tsarev сэнкс
Roman Tsarev не знаю, почему то прозевал момент, когда вы рассказали об этом в видео
Не совсем ясно зачем делить алгоритм на два случая. Вы говорите, что во втором случае нужно смотреть на последний символ образа, но ведь у нас было совпадение, т.е этот символ равен последнему символу строки. И выходит, что в любом случае мы сдвигаемся на d = последнему символу строки. Поправьте, если где-то ошибаюсь
@@romantsarev1145 вот оно как. спасибо за уточнение
Непонятно зачем в примере с метадата выносить как отдельный случай, можно обобщить, в случае несовпададеня образца и подстроки, смещение по самому правому элементу подсторки
Аналогично с последний буквой образца, достаточно сказать что при создании таблицы сдвигов это последний элемент(несчитая "прочие") для которого мы создаем
А так спасибо)
Для наглядности. Пожалуйста.
Все сдвиги надо увеличить на 1. И выбирать сдвиг по следующему за концом образца символу строки.
Почему?
Потому что сдвиги будут больше и не надо будет мудрить с последним символом образца.
При больших сдвигах важно мимо вхождения образа не проскочить. Не случится ли такого?
@@romantsarev1145 Не случится
@@user-pv4ns7oz6h Супер, если так!
Если несовпадающий символ не самый правый/последний в образе то
1. У вас: смещение берём по последнему символк образа
2. Вот тут ruclips.net/video/kvWFAZwZ_8U/видео.html : по несовпадающему символу образа
3. А вот тут ruclips.net/video/N6G6HVwJ4wQ/видео.html : по несовпадающему символу СТРОКИ
Почему такие разночтения ?
Я от оригинальной статьи авторов алгоритма отталкивался. Про авторов других видео не скажу.
@@romantsarev1145 можете ссылку дать ?
автор живёт рядом с жд (просто факт)
😂
9:08 фотошоп
В каком смысле? А так, все сделано в Power Point
@@romantsarev1145 ошибся
Ору, в случае когда нет ряда совпадений, сдвигаем по последнему символу строки, а если есть ряд совпадений, то сдвигаем по последнему символу образа, который РАВЕН последнему символу строки 👍👍👍
А можно хотя бы разобраться в алгоритме прежде чем записывать видео?))))
Не ори, все там правильно. Давай временную метку, поясню, что там у тебя не сходится.
Не стал дожидаться ответа, раз у тебя возник такой вопрос, возможно и у других он появится.
Первый случай 6:58
При несовпадении символ в строке «н»,
символ в образе «е»
сдвиг определяем по символу строки «н».
Второй случай 9:23
При несовпадении символ в строке «е»,
символ в образе «а»
сдвиг определяем по последнему символу образа «а».
В твоем комментарии-вопросе два существенных косяка:
«Ору, в случае когда нет ряда совпадений, сдвигаем по последнему символу строки…». Не по ПОСЛЕДНЕМУ символу строки, а по ТЕКУЩЕМУ символу строки;
«…, а если есть ряд совпадений, то сдвигаем по последнему символу образа, который РАВЕН последнему символу строки».
Да, сдвигаем по последнему символу образа, он точно НЕ РАВЕН текущему символу строки, а равен он ПОСЛЕДНЕМУ символу строки или нет, нас не интересует.
Нас вообще никогда не интересует ПОСЛЕДНИЙ символ строки. На последней итерации у него есть шанс стать текущим, но и тогда нам все равно последний он или нет, рассматриваем его так же, как рассматривали остальные символы строки до этого.
Как ты вообще видео смотрел?!
@@romantsarev1145 у него аниме на аватарке, все нормально