#1. Алгоритм Кнута-Морриса-Пратта (КМП-алгоритм) | Алгоритмы на Python

Рассматривается работа алгоритма Кнута-Морриса-Пратта с подробным объяснением принципов его функционирования для поиска образа в строке. Приводится реализация этого алгоритма на языке Python.
algorithm-kmp.py: github.com/selfedu-rus/python...

[@user-fd8yb4xw1v]

Сергей, спасибо большое. Вы так разорите товарищей с платных курсов

[@kadabrochka1252]

Не разорит. Практически тот же самый курс и материал есть на канале у Roman Tsarev (и выложен он еще 6 лет назад). Однако, мне нравится манера Сергея излагать материал.

[@mrfang5908]

Увидел свежее видео, пошел в плейлист, Сергей такое ощущение что вы прям выкладываете что мне надо, спасибо, хорошо объясняете

[@sergey6453]

Спасибо, очень доступно объясняете, прекрасная наглядная презентация, а также большое количество примеров и пояснений. Все в миг стало понятно!

[@user-ou7pi2wp8n]

Сергей, спасибо большое! Очень подробное и понятное объяснение! Каждый момент, который бы мог стать сложным, с Вашей подачей абсолютно понятен. Благодаря Вашим курсам и видеороликам получаю зачеты и пятерки на экзаменах в университете =) Спасибо еще раз)

[@s979n2]

Спасибо за труд! Отличное объяснение

[@nikolaytalkov2525]

Класс испытал истинное удовольствие от просмотра видео, четко ясно информативно. Спасибо тебе, так держать, молодец что снимаешь такие познавательные видео

[@MarchelloCSKAMoscow]

Сергей , вашей продуктивности можно позавидовать!

[@user-he9wc5pq3f]

Спасибо большое! Наконец-то я поняла этот алгоритм и связь префиксов и суффиксов)

[@user-mu8wd3vn8s]

Благодаря вам понял тонкий момент КМП, спасибо большое!

[@alexk.6243]

Классный урок, интересная и содержательная подача!

[@user-jo2ux1tm9y]

Очень круто объясняешь! Спасибо за уроки!

[@levinowak]

Коммент в поддержку! Лучшее объяснение и отличная подача

[@logistloglab5243]

Надеюсь, что дорос до этого плейлиста. Сергей, спасибо!)

[@evgenybratkovsky1486]

Очень толково объясняете. Спасибо!

[@luckytima2315]

Ой супер вообще ))) Надеюсь будет много видео в данной рубрике :))

[@Yornero]

Классный алгоритм, прекрасный в своей простоте. Помню решал схожую задачу, но через хэширование

[@justyar5781]

Как раз сейчас алгоритмы смотрю = ) Спасибо за материал!

[@dmitrykashlakov3831]

Очень хорошо объясняете

[@Noklee]

Начал смотреть за пару дней до олимпиады. Круть

[@user-ty4nc7fk5q]

Спасибо за такое классное объяснение 🔥

[@donfedor007]

Добрый день! не смотрел пока весь в Flask и Django, но лайк однозначно!!!

[@chimchimsterschannel161]

Сложно с первого раза понять) сегодня реализовал за O(m*n), надеюсь вскоре получится реализовать за О(m+n)) Сергей, спасибо вам большое, особенно за курс по ООП)

[@user-vu7hz8hg1u]

На счет знание алгоритмов это в первую очередь я с вами соглашусь уважаемый

[@user-ee1lx1pe7n]

Вы просто Гений!! Спасибище!!!

[@Vlad1998996]

Сложно, но гениально.

[@nemo917]

Большое спасибо за видео!

[@user-ej3iz3ty9g]

Красиво) Спасибо Вам большое)

[@ryzhakovalexey5037]

Я до сих пор не понимаю, почему так мало просмотров у тебя на канале

[@sainco3036]

Скоро будет много просмотров, а пока можно поддержать автора спонсорством.

[@user-fn9vr6ef4v]

Учеба дело очень энергозатратное)) Мозг обывателя гораздо охотнее поглощает тик-ток))

[@Grigoryshaw]

Ответ прост: очень мало заинтересованных этой темой

[@rpuropu]

гениальный алгоритм).. сигарета потухла давно) перематывал раз 20..)

[@michaelshulga5560]

за алгоритмы однозначно лайк

[@kpacccavchik]

ничего не понял, но так интересно, что поскорее хочется начать изучать )

[@study_land_pinsk1004]

Сергей, вы вылучший! Пол года уже изучаю Python и ML по разным русскоязычным и англоязычным курсам. Как устроюсь на работу обязательно отблагодарю "$ THANKS" )

[@user-wg2tb1hy6g]

Устроился?

[@fyyann5944]

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

[@hunya_k]

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

[@user-ee1lx1pe7n]

Этот алгоритм легче понять, если пропустить через дебаггер в пайчарме. Я его перезаписал с более наглядными названиями переменных. Если поставить на 28й строчке точку дебага и пошагово пройтись через Step Over (fn + F8 на маке) то все будет четко понятненько: ``` entry = "лилила" text = "лилилось лилилась" len_entry = len(entry) len_text = len(text) def get_pi(): pi = [0] * len_entry j, i = 0, 1 while i < len_entry: if entry[j] == entry[i]: pi[i] = j + 1 i += 1 j += 1 else: if j == 0: pi[i] = 0 i += 1 else: j = pi[j - 1] return pi text_pointer = 0 entry_pointer = 0 while text_pointer < len_text: if text[text_pointer] == entry[entry_pointer]: text_pointer += 1 entry_pointer += 1 if entry_pointer == len_entry: print("образ найден") break else: if entry_pointer > 0: pi = get_pi() entry_pointer = pi[entry_pointer - 1] else: text_pointer += 1 if text_pointer == len_text and entry_pointer != len_entry: print("образ не найден") ```

[@wadahalgabri560]

Спасибо Очень помогло !

[@versus666jzx]

13:40 не совсем корректно звучит "пи от нуля" и т.д. в данном случае, тут же все таки индексы некоторого списка, а не функция) Огромное спасибо за труд, все очень доходчиво!

[@user-wm3sb9gj7q]

спасибо огромное!

[@nikitabbrv5947]

Хочется весь плейлист сразу в оперативку себе подгрузить)

[@greentea2619]

лучше в жесткий будет конечно

[@user-pd8te8cu8o]

потрясающе

[@TheSadmint]

спасибо за видео! А регулярные выражения именно этот алгоритм используют?

[@plunk6774]

Спасибо за ролик, очень понятно! А как вы учили алгоритмы?

[@viktorzherekhin8590]

Для целей обучения полезно взять описание алгоритма и пытаться самому реализовать его на Пайтон. И потом проверить, чтобы получился одинаковый результат. Т.к. одно и то же можно реализовать по-разному. Тот же список, к примеру, можно заранее задать с конкретными элементами (нулями, к примеру), а можно формировать в процессе выполнения цикла (pi.append(0)). Можно сделать через цикл for, можно - через while, и т.д.

[@silentlyow]

Еще можно на основе хэшей, посчитать хэш строки и хэш того что нужно найти и уже пройтись по строке и посмотреть есть ли одинаковые, сложность O(n)

[@1984Nik1]

супер

[@user-vu7hz8hg1u]

Хотелось бы по-больше инфы по алгоритмам

[@pythonofsky4545]

Классно! Жаль, невелик список алгоритмов в плэйлисте.

[@slava_zxz]

Спасибо

[@MrIgor989]

Ты гений

[@DDR4605]

Посмотрел один раз, потом записал конспект, потом решил одну задачку со шпорой, смотрю второй раз. Начал что-то понимать…😮

[@andreiviltouski2390]

👍

[@nullnull557]

Почему-то момент j = p[j-1] никто не обсуждает, хотя именно к нему нужно уделить внимание в первую очередь. Не понятно как к нему пришли

[@nullnull557]

Если префикс не подошёл, тогда нужно ее длину уменьшить. Максимально эффективно брать длину максимального префикса для самого префикса.

[@ankhmarcius8331]

если уже смотрел алгоритм в питоне, то понимаешь что m=len(a), в видео же, не оговаривается о какой m идет разговор, и почему j=m

[@ShadowStormlq5mwdasd]

Интересно в чём и как Вы делаете ваши уроки?

[@alphonsecapone8218]

Доброго времени суток) Прошу прощения и ни на что не претендую, просто учусь и стараюсь разобраться. Из того что я на данный момент понял про концепцию большого О - умножение подразумевает под собой вложенный цикл. А в прямом поиске его нет (по крайней мере в версии, которую я попробовал написать). И получается что его сложность в общем случае зависит только от размера источника поиска - О(n). Это может хоть как-то быть правильно? Просто я попробовал замерить скорости у этих алгоритмов и из кучи прогонов только раз смог добиться того чтобы КМП обогнал прямой и то только когда сделал для него все условия (красивые, для больших пропусков, повторения букв и всё такое).

[@ubershh]

Концепция Big O подразумевает не в общем случае, а "в худшем случае", а при прямом поиске для каждой буквы строки в худшем случае придется проходится по каждой букве образца, отсюда и получается O(m*n)

[@nitra-hl2fj]

Видео хорошее, только непонятно: зачем вынесли последнее условие из цикла while? Образ "лилила" в конце строки "лилилось лилила" одновременно выдаст и "образ найден" и "образ не найден"

[@selfedu_rus]

Да, согласен, недосмотрел! Можно поправить вот так: if i == n and j != m: Условие вне цикла, чтобы не выполнять лишние операторы в теле цикла. Исправил программу на github.

[@dvd6307]

Да ты серьезно? Я не успел ещё посмотреть остальные плейлисты, а тут новое. Круто конечно, но... Что мне делать?

[@viktorkomlev5804]

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

[@sainco3036]

Жаль, django закончилось, я только вошел во вкус)

[@UrTa91]

Ну пожалуйста можно в темном цвете делать презентация смотрю ночью мне пипец как ярко

[@bonie3044]

я смотрел твой плейлист по flask как я тут оказался?

[@MrJannes]

Мы префикс функцию используем только один раз или после каждого при "прикладывания" образца к тексту?

[@selfedu_rus]

префиксы формируются на 1-м этапе до поиска образца, затем, на 2-м этапе при несовпадении символов используется сдвиг на вычисленный префикс на 1-м этапе

[@RedkeiGost]

Только в английской Википедии и нагуглил упомянание, что Кнут в примечаниях работы "Selected Papers on Design of Algorithms" писал про Матиясевича. И больше ничего. Найти бы ещё какой-то материал, подробнее да убедительнее. Если он первый опубликовал, то где он опубликовал? В той же Википедии ссылка на Кнута и работу Матиясевича 1971 года.

[@RedkeiGost]

@@deniskamal подробнее, это когда больше подробностей.

[@RedkeiGost]

@@deniskamal которые убеждают. Очевидно же.

[@user-wl6mp6nk2m]

Так какой алгоритм лучше: КМП или БМХ ?

[@user-pg6mb6il1c]

Давай джанго , плиз

[@user-ny9ux9ss8n]

Это где применяется ? В каких проектах ?

[@begula_chan]

Можно регулярным выражением сделать

[@ceo-s]

Подскажите пожалуйста, зачем всё таки брать п[ j-1 ] при формировании массива п если можно просто поставить 0. Префиксы то всё равно все сначала идут

[@DDR4605]

Это условие если j>0

[@tenelokis]

Полчаса пролетели за минуту 🙂

[@RocetDev]

Привет друг. Я тебе рекомендую сделать свой курс на stepik что бы прибавить аудиторию

[@selfedu_rus]

Спасибо, в ближайших планах )

[@riplock77]

Сдравстуйте, подскажите пожалуйста как сделать чтобы при запуске PyCharm запускалось главное меню с проектами а не запускался последний проект 🙏

[@doloidiktatorov]

File Settings Appearance & Behavior System Settings Startup/Shoutdown Reopen last project

[@user-ji3et9wq1y]

не могу понять логику подсчета количества операций при пошаговом сравнении. если длина массива исходного массива n , а длина образа m , как мы получаем сложность n*m. При каждом сдвиге количеcтво операций равно m(длина образа), число сдвигов образа получим вычитанием длины образа из длины исходной строки, плюс один (n-m+1)*m. При данном примере получается 72+15=87. Максимальная сложность по видео равна 17*6=102, данную разницу вы игнорируете как не значительную? Или я не правильно считаю?

[@ShadowStormlq5mwdasd]

Этот алгоритм используется в python? Например в str.find() и всех похожим функциям? Кто знает?

[@licantrop609]

Скорее всего в str.__contains__() используется.

[@owenearmusic]

Мое лицо когда пытаюсь осознать этот алгоритм 6:42

[@dazdess]

А можно ли тут обойтись регулярными выражениями? Насколько этот алгоритм будет быстрее работать чем регулярные выражения?

[@selfedu_rus]

Если просто найти образец в строке, то подобные алгоритмы будут работать быстрее регулярок. (При условии, что программа делается на С++, а не Python). Если же используете Python, то опять же, лучше брать соответствующие методы строк: count(), index(), find() и т.п. Регулярные - это более изощренный инструмент для тонкой обработки.

[@user-hr8vo2jy5c]

Регулярные выражения?

[@stas-web]

Реализация на JS: function kmp(text, str) { const N = text.length, M = str.length; let p = new Uint16Array(str.length); for (i = 1, j = 0; i < M; i++) { while (j > 0 && str[j] != str[i]) j = p[j-1]; if(str[j] == str[i]) j++; p[i] = j; } for (i = 0, j = 0; i < N; i++) { while (j > 0 && str[j] != text[i]) j = p[j - 1]; if (str[j] == text[i]) j++; if (j == M) return i - j + 1; } return -1; } console.log(kmp('лилилось лилилась', 'лилила')); // 9

[@janibektursynbaev]

пишет не найдено

[@user-rf9nl9bl4j]

Скажите пожалуйста в какой программе пишите код

[@selfedu_rus]

PyCharm

[@user-ox7kc4fd1m]

интересно почему этот вариант не работает h1 = "ллилилась лилилось" h2 = "лилилась" a=0 b=1 c=2 d=3 e=4 f=5 g=6 k=7 l=8 for i in range(len(h1)-len(h2)-1): uo = h1[a]+h1[b]+h1[c]+h1[d]+h1[e]+h1[f]+h1[g]+h1[k]+h1[l] if h2 == uo: print('gotovo') a = a + 1 b = b + 1 c = c + 1 d = d + 1 e = e + 1 f = f + 1 g = g + 1 k = k + 1 l = l + 1

[@whitepepper742]

а в чем логика здесь вообще? зачем мы каждой отдельной буквой обозначаем номер буквы образца? Зачем здесь инициализация uo, если оно используется один раз? Ну и главный вопрос, если образец будет из, допустим, 99 букв, вы будете каждый номер буквы образца инициализировать отдельно? зачем нам 99 переменных? Ничего не понятно. И читаемость кода ужасная

[@janibektursynbaev]

в чем тут ошибка? #include using namespace std; string find(string s, string a, vector pi){ int i = 0; int j = 0; while(i

[@user-ec5nx5gd2j]

А я ничего не поняла

[@maiorchiks3107]

ничего не понял (((

[@user-gd4en4ot3u]

так себе понятно... хотя это не удивительно, ведь речь идет об алгоритмах. Самое бесячее, что нельзя задать какой то вопрос в моменте

[@lubovd5335]

Матиясевич Советский ученый, а не русский

[@selfedu_rus]

Русскую национальность никто не отменял, см. в википедии: ru.wikipedia.org/wiki/Матиясевич,_Юрий_Владимирович

[@user-st7gn4yk8q]

Python - это хорошо, но JS ещё лучше)

[@fghinty7623]

а?

[@nadyamoscow2461]

JS тут тоже есть. Правда, не знаю, чем оно лучше, чем Python

[@fontyfx6843]

Наоборот

[@whitepepper742]

Опять гонки какой язык лучше🤡Под определенную задачу свой язык

[@user-un8ns5uc9j]

А если сравнивать текст с образцом по букве а и в случае совпадения сравнивать всё?