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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Этот алгоритм легче понять, если пропустить через дебаггер в пайчарме. Я его перезаписал с более наглядными названиями переменных. Если поставить на 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("образ не найден") ```

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

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

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

потрясающе

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

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

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

Спасибо

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

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

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

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

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

супер

Ты гений

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

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

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

👍

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализация на 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

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

интересно почему этот вариант не работает 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

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

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

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

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

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