Алгоритм Кнута-Морриса-Пратта 

Пожалуйста!

вот именно. потому что на лекциях и в книге надо напрячь мозги и УВИДЕТЬ, что тут можно провернуть хитрость и выиграть в скорости, не делая лишних действий. а в видео тебе УКАЗЫВАЮТ, что вот она хитрость. да и в этом видео, только половину хитрости при поиске показали, остальную хитрость при быстрейшем заполнении pi-массива тихонько утаили, сразу реализацию выдав.

@@tayzlelavarez6848 Да куда уже подробнее то?!

@@romantsarev1145 да лан, нормально. спасибо.

Пожалуйста. Я старался.

Та же история с Виртом ) Пожалуйста!

Супер! Рад, что помог.

Пожалуйста

Значит своей цели я достиг 😇

Спасибо. Очень приятный отзыв!

Пожалуйста!

Пожалуйста

Пожалуйста!

Спасибо!

Охх, вижу кто-то тоже прямо сейчас алгоритмы изучает :) Автор молодец, большое ему спасибо, тоже понял благодаря ему.

Спасибо

От всего сердца!

Я рад, что пригодилось

Пожалуйста!

Пожалуйста

Нестареющая (с 1967 года) классика!

Пожалуйста!

Пожалуйста!

Nice!

Пожалуйста

Оговорился, когда записывал. Правильно, как на слайде, 1969. Перезаписывать не стал, потому-что на тот момент звук выстроить не смог бы. Однако, если Вы так внимательно слушали, то должны были заметить, что я подчеркиваю, что Матиясевич продолжил этот алгоритм ранее Кнута, Морриса и Пратта. А они это сделали в 1970, опубликовали в 1977. Так что 1989 однозначно отпадает. 🎉

За видео пожалуйста. Ваш вопрос не понял. В ролике я сначала даю общее описание этапа, а следом его же программную реализацию. Например, в общем описании - последовательно переберем все символы образа, а в последующем описании программной реализации - возьмем целочисленную переменную i, у которой будут меняться значения от 0 до N-1, где N - количество символов в образе. То есть ничего не убавляю и не добавляю, а показываю как программно реализовать то, о чем только что рассказывал.

Спасибо. А что такое шарага?

Здравствуйте, спасибо за видео. Шарагой называют место для получения среднего профессионального образования)

@@user-tr6tp5qy7y в данном случае я иронично назвал шарагой место для получения высшего образования

Пожалуйста!

Здравствуйте! Покажет в любом случае, что образа в строке нет.

Пожалуйста

Искать первое вхождение или все - зависит от постановки задачи и, в общем-то, от программиста, а не алгоритма КМП. При этом еще нужно определиться, как считать вхождения. Например, сколько вхождений образа "aa" в строке "aaaa", два или три? Насчет программы на Python, на Ваше усмотрение.

@@romantsarev1145 Если нужно найти ВСЕ вхождения и нет дополнительных условий, наверное, нужно искать все вхождения :) Что бы ответить на вопрос сколько "аа" входит в строку "аааа" можно запустить прямой поиск и он даст однозначный ответ (AAaa ,aAAa, aaAA), странно, если КМП выдаёт что-то другое ИМХО. К КМП нужно было обратиться, чтобы снизить сложность с O(m*n) при прямом поиске до O(m+n) при КМП.

вроде правильно работает поиск пи функции от суммы подстроки и строки с разделителем(f(sub+'#'+s)), совпадения при значении равном длине подстроки, про скорость не могу сказать

@@kotokotfgcscrub Они все правильно работают, вопрос только в реализации и конечно в сложности(скорость не совсем тот параметр, сильно зависит от входящих данных)

Пожалуйста!

У нас есть префикс для `s[i - 1]` равный `k = π[i - 1]`. Как длина он указывает сколько символов в макс префиксе `i - 1`, как индекс он указывает на символ, *следующий* за префиксом. На `i`-ой итерации мы "приписываем" символ справа к префиксу и суффиксу. Если символы одинаковые - всё просто - префикс увеличился на 1. Если разные, значит текущие префикс и суффикс не равны и отличаются только последнем символом (до этого же были равны). Тогда они могут перекрываться "кусочками" меньшей длины, т.е. иметь общий префикс/суффикс более короткий на отрезке `s[0, k)`. Откуда его взять? У нас есть старый `π[i - 1] = k` НОП, который указывает на следующий символ после НОП-а. Нам надо найти НОП в подстроке `s[0, k)` т.к. перекрытие "куском" будет именно там, поэтому берем `π[k - 1]` и сравниваем только последние символы. Т.е. если текущие префикс/суффикс не равны, мы берем НОП для подстроки предыдущего префикса, увеличиваем на символ и сравниваем с "куском" нового суффикса. Т.е. если `s[k] != s[i]` то `s[π[k - 1]] ?= s[i]`. И так до конца.

Так, вроде, есть уже такие.

Конечно, найдет. Вообще, идея алгоритмов этого класса - шагнуть как можно дальше при несовпадении, при этом, естественно, не пропустить вхождения образа в строку.

не работает не из-за длинны, а просто алгоритм для моей задачи не предназначен :) Ну или я не вижу, как применить пока. Если даже взять пример из видео "abbaabbab" который выдает хороший результат и добавить просто любую не использованную дальше букву к примеру так "cabbaabbab", то всё становится нулями. Так и должно быть?

В общем, решил всё с помощью суффиксного дерева(Алгоритм Уконена). Оно вообще многое может, по сути мульти-решатель многих задач. Переделал с обработки символов, на обработку массива и теперь можно любой массив с данными выстроить в дерево и делать интересные вещи с этим массивом. Просто достаточно compare-функцию определить для обработки сравнения и всё. Всем советую! ;)

Thumbs up

1969 верно. Было уже не исправить.

Уж как мог 😇

@@romantsarev1145 спасибо вам! без этого объяснения так быстро бы не разобрался

@@user-ks9gf1lc6l Пожалуйста!

Число символов в строке, т.е. в тексте, в котором ищем образ.

Спасибо

Верно

Тут с наскока не взять. Особенно, если сонный. Так что высыпайся, а завтра со свежими силами... Ну, если что будет непонятно, пиши, проконсультирую.

А это, между прочим, самое понятное видео на русском об алгоритме КМП