Алгоритм Бойера-Мура-Хорспула

[@ПетроваНаталья-с3п]

Спасибо большое! Самое ясное объяснение данного алгоритма)

[@romantsarev1145]

Пожалуйста!

[@ВикторияБондаренко-т6г]

Большое спасибо!!! Просто, наглядно и понятно! Ваше видео очень помогло, наконец-то написала нормальный рабочий алгоритм поиска))

[@romantsarev1145]

Пожалуйста! Ставьте лайк, подписывайтесь на канал )

[@МаксимГлотов-р8к]

Роман, спасибо вам за такое понятное объяснение, благодаря вашим видео я наконец разобрался с такими алг как этот и КМП

[@romantsarev1145]

Пожалуйста.

[@Rivrabobra]

Вы отлично объясняете. Спасибо!

[@romantsarev1145]

Спасибо за лестную оценку.

[@rajahbtw]

Спасибо большое, помогло

[@romantsarev1145]

Пожалуйста!

[@ТимофейПшеничный]

Спасибо! Очень понятно!

[@romantsarev1145]

Пожалуйста!

[@veronikabykova5494]

большое спасибо! теперь все точно уложилось в голове))

[@romantsarev1145]

Пожалуйста.

[@veronikabykova5494]

Можно вопрос, а не нужно удалять пробелы, прежде чем применять алгоритм? То есть возможен вариант, когда сдвиг слова по таблице смещений поставит его так, что последний символ образа будет сравниваться с пробелом - что в таком случае?

[@romantsarev1145]

Прекрасный вопрос! Для ответа на него рассмотрим программную реализацию. При формировании массива d я использовал таблицу ASCII (11:50). Если взглянуть на нее, то можно увидеть, что пробел имеет код 32. То есть для ЭВМ пробел - это такой же символ как и любая буква, цифра, знак препинания (которые, естественно, имеют свои коды). Так что пробелы предварительно удалять не нужно. Более того, образ может быть не отдельным словом, а фразой и, конечно, будет содержать пробелы, которые тоже удалять не нужно.

[@АлёнаКоломийцева-п2о]

Суупер! Спасибо😊 очень понятно и наглядно)

[@romantsarev1145]

Пожалуйста

[@БахтиярТутенов-щ8ц]

Крутое видео! А то читаешь и ничего не понимаешь))

[@RedPixel-j1e]

Супер! Спасибо!

[@romantsarev1145]

Пожалуйста!

[@Federation1323]

выглядит как какая-то магия)))

[@romantsarev1145]

Это она и есть

[@nicivanov5135]

Подскажите, алгоритм sha 256 тоже на сдвиге работает или другие алгоритмы использует? Нужно понять сам принцып работы hashlib.

[@romantsarev1145]

Я не в курсе, если честно

[@nicivanov5135]

@@romantsarev1145 kzbin.info/www/bejne/o5PInIBoetd7nK8

[@yuriysosnovskiy2118]

На сколько нужно сдвигать индекс при нахождении элемента, если нужно найти несколько вхождений?

[@romantsarev1145]

Все зависит от Вашей постановки задачи. Если Вы считаете, что в строку "аааа" образ "аа" входит три раза, тогда на один символ. А, если входит два раза, тогда начинайте с символа, который стоит сразу за совпавшей частью строки и образа. В целом, алгоритм ищет первое совпадение образа и строки, остальное на усмотрение программиста.

[@yuriysosnovskiy2118]

@@romantsarev1145 я увеличивал индекс і (тот, который идёт по строке) на значение из таблицы сдвигов последнего совпавшего символа. Вроде работает нормально.

[@zedoo5699]

Спасибо, но кое что очень странно. В первом примере ты считаешь смещение относительно символов с строке, а во втором примере относительно образа

[@romantsarev1145]

Если при сравнении последнего символа образа и символа строки произошло несовпадение, то определяем сдвиг по символу строки (6:59); если же несовпадение произошло после того, как совпал ряд символов строки и образа, то сдвиг будет равен d, соответствующий последнему символу образа (9:17).

[@zedoo5699]

Roman Tsarev сэнкс

[@zedoo5699]

Roman Tsarev не знаю, почему то прозевал момент, когда вы рассказали об этом в видео

[@qvv3r7y77]

Не совсем ясно зачем делить алгоритм на два случая. Вы говорите, что во втором случае нужно смотреть на последний символ образа, но ведь у нас было совпадение, т.е этот символ равен последнему символу строки. И выходит, что в любом случае мы сдвигаемся на d = последнему символу строки. Поправьте, если где-то ошибаюсь

[@par9325]

@@romantsarev1145 вот оно как. спасибо за уточнение

[@АлександрШеремет-я7е]

Если несовпадающий символ не самый правый/последний в образе то 1. У вас: смещение берём по последнему символк образа 2. Вот тут kzbin.info/www/bejne/oae6d3SQrL-Sbrc : по несовпадающему символу образа 3. А вот тут kzbin.info/www/bejne/hGeqZ3uMrK9nrbM : по несовпадающему символу СТРОКИ Почему такие разночтения ?

[@romantsarev1145]

Я от оригинальной статьи авторов алгоритма отталкивался. Про авторов других видео не скажу.

[@АлександрШеремет-я7е]

@@romantsarev1145 можете ссылку дать ?

[@СергейСвердлов-у4в]

Все сдвиги надо увеличить на 1. И выбирать сдвиг по следующему за концом образца символу строки.

[@romantsarev1145]

Почему?

[@СергейСвердлов-у4в]

Потому что сдвиги будут больше и не надо будет мудрить с последним символом образца.

[@romantsarev1145]

При больших сдвигах важно мимо вхождения образа не проскочить. Не случится ли такого?

[@СергейСвердлов-у4в]

@@romantsarev1145 Не случится

[@romantsarev1145]

@@СергейСвердлов-у4в Супер, если так!

[@valera16011990]

Непонятно зачем в примере с метадата выносить как отдельный случай, можно обобщить, в случае несовпададеня образца и подстроки, смещение по самому правому элементу подсторки Аналогично с последний буквой образца, достаточно сказать что при создании таблицы сдвигов это последний элемент(несчитая "прочие") для которого мы создаем А так спасибо)

[@romantsarev1145]

Для наглядности. Пожалуйста.

[@milhot]

автор живёт рядом с жд (просто факт)

[@romantsarev1145]

😂

[@sominite]

9:08 фотошоп

[@romantsarev1145]

В каком смысле? А так, все сделано в Power Point

[@sominite]

@@romantsarev1145 ошибся

[@alexanderginger754]

Ору, в случае когда нет ряда совпадений, сдвигаем по последнему символу строки, а если есть ряд совпадений, то сдвигаем по последнему символу образа, который РАВЕН последнему символу строки 👍👍👍 А можно хотя бы разобраться в алгоритме прежде чем записывать видео?))))

[@romantsarev1145]

Не ори, все там правильно. Давай временную метку, поясню, что там у тебя не сходится.

[@romantsarev1145]

Не стал дожидаться ответа, раз у тебя возник такой вопрос, возможно и у других он появится. Первый случай 6:58 При несовпадении символ в строке «н», символ в образе «е» сдвиг определяем по символу строки «н». Второй случай 9:23 При несовпадении символ в строке «е», символ в образе «а» сдвиг определяем по последнему символу образа «а». В твоем комментарии-вопросе два существенных косяка: «Ору, в случае когда нет ряда совпадений, сдвигаем по последнему символу строки…». Не по ПОСЛЕДНЕМУ символу строки, а по ТЕКУЩЕМУ символу строки; «…, а если есть ряд совпадений, то сдвигаем по последнему символу образа, который РАВЕН последнему символу строки». Да, сдвигаем по последнему символу образа, он точно НЕ РАВЕН текущему символу строки, а равен он ПОСЛЕДНЕМУ символу строки или нет, нас не интересует. Нас вообще никогда не интересует ПОСЛЕДНИЙ символ строки. На последней итерации у него есть шанс стать текущим, но и тогда нам все равно последний он или нет, рассматриваем его так же, как рассматривали остальные символы строки до этого. Как ты вообще видео смотрел?!

[@OneOfWun-n2g]

@@romantsarev1145 у него аниме на аватарке, все нормально