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

[@devopserin]

Спасибо большое за Ваш труд и за такой классный структурированный материал! Всё понятно)

[@ИванЕвдокимов-л6ь]

Здравствуйте! Спасибо за ваш труд, только благодаря вам смог понять, почему работает этот алгоритм, а также самостоятельно реализовать его. Но у других в видео речь идет о разделении ситуаций на 2 случая, в зависимости от которых берется смещение по символу подстроки или искомой строки (ниже уже писали про это). Например: с 6:02 kzbin.info/www/bejne/oae6d3SQrL-Sbrc Можете прокомментировать, почему автор берет смещение "ы" вместо "т", которое должно браться в вашей версии алгоритма? Уже часа 3 туплю, пересматривая 2 видео и не понимая, почему оба варианта работают, если вы берете смещение для разных букв

[@oleksandrtsymbaliuk]

Я уже отвечал на этот вопрос(действительно ниже). Вот ссылка на оригинальную статью автора этого алгоритма - webhome.cs.uvic.ca/~nigelh/Publications/stringsearch.pdf Прочтите ее, посмотрите есть ли там упоминание о каких то двух случаях. Могу заранее ответить, что нет. Тут сама идея алгоритма, что бы откинуть вот эти лишние проверки. Чем руководствовались авторы других видео мне не ведомо, я читал оригинал статьи автора.

[@ИванЕвдокимов-л6ь]

@@oleksandrtsymbaliukСпасибо за ответ и статью - изучил и действительно не нашел ничего про 2 случая, странно. И за видео спасибо, очень помогло) Пойду смотреть весь ваш плейлист по алгоритмам

[@ИванЕвдокимов-л6ь]

@@oleksandrtsymbaliuk Кстати ниже предлагаю более лаконичный вариант формирования таблицы смещений (на Python), где используется алфавит не всей строки и подстроки (тем более когда заранее не известно про него), а только подстроки, из-за чего происходит экономия по памяти и нет неоходимости передавать start_index, end_index: def boyer_moore_horspool_searcher(subseq, seq) -> int: """Boyer-Moore-Horspool algorithm or Horspool's algorithm. Average-complexity: E(T(m, n)) = O(m/Z), where Z = len(set(subseq + seq)). Best case: O(n/m), worse case: O(m*n). Memory-complexity: O(Z_m), where Z_m = len(set(subseq)).""" offset_dict = create_offset_dict(subseq) i = m = len(subseq) - 1 while i < len(seq): if seq[i-m:i+1] == subseq: return i - m i += offset_dict.get(seq[i], len(subseq)) return -1 def create_offset_dict(lst) -> dict: offset_dict = {} for i in range(len(lst)-1): offset_dict[lst[i]] = len(lst) - (i + 1) return offset_dict

[@oleksandrtsymbaliuk]

Да использование словаря действительно значительно упрощает реализацию. Правда на момент публикации этого алгоритма в большинстве языков программирования не было словарей в стандартных библиотеках :). Но все должно развиваться, поэтому ваш вариант лаконичнее и компактнее.

[@liauao]

Здравствуйте! А можете рассказать про БПФ (и обратное БПФ), как многочлены перемножать, поиск подстроки в строке (алгоритмы)?

[@oleksandrtsymbaliuk]

Добрый день. Тут единственно, что можно сказать - что всему свое время. А вот алгоритмов по поиску подстроки в строке в разделе работа со строками у меня уже и так несколько.

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

Когда несовпадение наступает не по последнему символу подстроки а по любому другому то сдвиг надо определять не по несовпадающему символу из строки а по несовпадающему символу из подстроки. Не так ли ?

[@oleksandrtsymbaliuk]

Согласно этому алгоритму сдвиг всегда определяется тем символом (из основной строки) который соответствует (как стоит над символом при сравнении) последнему символу из искомой строки независимо от того в каком месте было несовпадение.

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

​​@@oleksandrtsymbaliuk Я не сам придумал kzbin.info/www/bejne/oae6d3SQrL-Sbrc отсюда взял, и отсюда kzbin.info/www/bejne/gXq4eYqDrMaph8k

[@oleksandrtsymbaliuk]

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

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

​@@oleksandrtsymbaliuk kzbin.info/www/bejne/oae6d3SQrL-Sbrc ВНИМАТЕЛЬНО ! 5:45....6:27

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

​@@oleksandrtsymbaliuk kzbin.info/www/bejne/gXq4eYqDrMaph8k внимательно м 8:25....

[@McMouse88]

мне кажется у данного алгоритма по сравнению с KMP довольно много недостатков )

[@DMITRIY1991GOD]

Я думал, все украинские каналы перекатились на украинский язык. Не страшно на вражеской мове балакать?)

[@oleksandrtsymbaliuk]

В моей стране если ты украинец и любишь свою страну, то можешь говорить на любом языке.