#1. Алгоритм Кнута-Морриса-Пратта (КМП-алгоритм) | Алгоритмы на Python
Рассматривается работа алгоритма Кнута-Морриса-Пратта с подробным объяснением принципов его функционирования для поиска образа в строке. Приводится реализация этого алгоритма на языке Python.
algorithm-kmp.py: github.com/selfedu-rus/python...
Пікірлер: 112
Сергей, спасибо большое. Вы так разорите товарищей с платных курсов
@kadabrochka1252
22 күн бұрын
Не разорит. Практически тот же самый курс и материал есть на канале у Roman Tsarev (и выложен он еще 6 лет назад). Однако, мне нравится манера Сергея излагать материал.
Спасибо за труд! Отличное объяснение
Сергей , вашей продуктивности можно позавидовать!
Увидел свежее видео, пошел в плейлист, Сергей такое ощущение что вы прям выкладываете что мне надо, спасибо, хорошо объясняете
Спасибо, очень доступно объясняете, прекрасная наглядная презентация, а также большое количество примеров и пояснений. Все в миг стало понятно!
Сергей, спасибо большое! Очень подробное и понятное объяснение! Каждый момент, который бы мог стать сложным, с Вашей подачей абсолютно понятен. Благодаря Вашим курсам и видеороликам получаю зачеты и пятерки на экзаменах в университете =) Спасибо еще раз)
Класс испытал истинное удовольствие от просмотра видео, четко ясно информативно. Спасибо тебе, так держать, молодец что снимаешь такие познавательные видео
Благодаря вам понял тонкий момент КМП, спасибо большое!
Спасибо большое! Наконец-то я поняла этот алгоритм и связь префиксов и суффиксов)
Очень толково объясняете. Спасибо!
Очень круто объясняешь! Спасибо за уроки!
Классный урок, интересная и содержательная подача!
Коммент в поддержку! Лучшее объяснение и отличная подача
Надеюсь, что дорос до этого плейлиста. Сергей, спасибо!)
Очень хорошо объясняете
Этот алгоритм легче понять, если пропустить через дебаггер в пайчарме. Я его перезаписал с более наглядными названиями переменных. Если поставить на 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 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 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("образ не найден") ```
Ой супер вообще ))) Надеюсь будет много видео в данной рубрике :))
Начал смотреть за пару дней до олимпиады. Круть
Классный алгоритм, прекрасный в своей простоте. Помню решал схожую задачу, но через хэширование
Добрый день! не смотрел пока весь в Flask и Django, но лайк однозначно!!!
Спасибо за такое классное объяснение 🔥
Как раз сейчас алгоритмы смотрю = ) Спасибо за материал!
Сложно с первого раза понять) сегодня реализовал за O(m*n), надеюсь вскоре получится реализовать за О(m+n)) Сергей, спасибо вам большое, особенно за курс по ООП)
Вы просто Гений!! Спасибище!!!
На счет знание алгоритмов это в первую очередь я с вами соглашусь уважаемый
Сложно, но гениально.
Большое спасибо за видео!
Красиво) Спасибо Вам большое)
Я до сих пор не понимаю, почему так мало просмотров у тебя на канале
@sainco3036
3 жыл бұрын
Скоро будет много просмотров, а пока можно поддержать автора спонсорством.
@user-fn9vr6ef4v
Жыл бұрын
Учеба дело очень энергозатратное)) Мозг обывателя гораздо охотнее поглощает тик-ток))
@Grigoryshaw
Жыл бұрын
Ответ прост: очень мало заинтересованных этой темой
за алгоритмы однозначно лайк
спасибо за видео! А регулярные выражения именно этот алгоритм используют?
Спасибо, очень понятно!
Сергей, вы вылучший! Пол года уже изучаю Python и ML по разным русскоязычным и англоязычным курсам. Как устроюсь на работу обязательно отблагодарю "$ THANKS" )
@user-wg2tb1hy6g
11 ай бұрын
Устроился?
@fyyann5944
10 ай бұрын
Тоже интересно Решил изучать питон, ибо тема интересна и привлекает идея работать в айти
гениальный алгоритм).. сигарета потухла давно) перематывал раз 20..)
Для целей обучения полезно взять описание алгоритма и пытаться самому реализовать его на Пайтон. И потом проверить, чтобы получился одинаковый результат. Т.к. одно и то же можно реализовать по-разному. Тот же список, к примеру, можно заранее задать с конкретными элементами (нулями, к примеру), а можно формировать в процессе выполнения цикла (pi.append(0)). Можно сделать через цикл for, можно - через while, и т.д.
ничего не понял, но так интересно, что поскорее хочется начать изучать )
Спасибо Очень помогло !
13:40 не совсем корректно звучит "пи от нуля" и т.д. в данном случае, тут же все таки индексы некоторого списка, а не функция) Огромное спасибо за труд, все очень доходчиво!
Почему-то момент j = p[j-1] никто не обсуждает, хотя именно к нему нужно уделить внимание в первую очередь. Не понятно как к нему пришли
@nullnull557
Жыл бұрын
Если префикс не подошёл, тогда нужно ее длину уменьшить. Максимально эффективно брать длину максимального префикса для самого префикса.
Спасибо за ролик, очень понятно! А как вы учили алгоритмы?
потрясающе
спасибо огромное!
Хочется весь плейлист сразу в оперативку себе подгрузить)
@greentea2619
3 ай бұрын
лучше в жесткий будет конечно
Спасибо
Еще можно на основе хэшей, посчитать хэш строки и хэш того что нужно найти и уже пройтись по строке и посмотреть есть ли одинаковые, сложность O(n)
супер
Интересно в чём и как Вы делаете ваши уроки?
Ты гений
Хотелось бы по-больше инфы по алгоритмам
Доброго времени суток) Прошу прощения и ни на что не претендую, просто учусь и стараюсь разобраться. Из того что я на данный момент понял про концепцию большого О - умножение подразумевает под собой вложенный цикл. А в прямом поиске его нет (по крайней мере в версии, которую я попробовал написать). И получается что его сложность в общем случае зависит только от размера источника поиска - О(n). Это может хоть как-то быть правильно? Просто я попробовал замерить скорости у этих алгоритмов и из кучи прогонов только раз смог добиться того чтобы КМП обогнал прямой и то только когда сделал для него все условия (красивые, для больших пропусков, повторения букв и всё такое).
@ubershh
2 жыл бұрын
Концепция Big O подразумевает не в общем случае, а "в худшем случае", а при прямом поиске для каждой буквы строки в худшем случае придется проходится по каждой букве образца, отсюда и получается O(m*n)
Классно! Жаль, невелик список алгоритмов в плэйлисте.
Только в английской Википедии и нагуглил упомянание, что Кнут в примечаниях работы "Selected Papers on Design of Algorithms" писал про Матиясевича. И больше ничего. Найти бы ещё какой-то материал, подробнее да убедительнее. Если он первый опубликовал, то где он опубликовал? В той же Википедии ссылка на Кнута и работу Матиясевича 1971 года.
Видео хорошее, только непонятно: зачем вынесли последнее условие из цикла while? Образ "лилила" в конце строки "лилилось лилила" одновременно выдаст и "образ найден" и "образ не найден"
@selfedu_rus
3 жыл бұрын
Да, согласен, недосмотрел! Можно поправить вот так: if i == n and j != m: Условие вне цикла, чтобы не выполнять лишние операторы в теле цикла. Исправил программу на github.
я смотрел твой плейлист по flask как я тут оказался?
👍
Мы префикс функцию используем только один раз или после каждого при "прикладывания" образца к тексту?
@selfedu_rus
3 жыл бұрын
префиксы формируются на 1-м этапе до поиска образца, затем, на 2-м этапе при несовпадении символов используется сдвиг на вычисленный префикс на 1-м этапе
если уже смотрел алгоритм в питоне, то понимаешь что m=len(a), в видео же, не оговаривается о какой m идет разговор, и почему j=m
Так какой алгоритм лучше: КМП или БМХ ?
Это где применяется ? В каких проектах ?
Посмотрел один раз, потом записал конспект, потом решил одну задачку со шпорой, смотрю второй раз. Начал что-то понимать…😮
Подскажите пожалуйста, зачем всё таки брать п[ j-1 ] при формировании массива п если можно просто поставить 0. Префиксы то всё равно все сначала идут
@DDR4605
6 ай бұрын
Это условие если j>0
Сдравстуйте, подскажите пожалуйста как сделать чтобы при запуске PyCharm запускалось главное меню с проектами а не запускался последний проект 🙏
@doloidiktatorov
3 жыл бұрын
File Settings Appearance & Behavior System Settings Startup/Shoutdown Reopen last project
не могу понять логику подсчета количества операций при пошаговом сравнении. если длина массива исходного массива n , а длина образа m , как мы получаем сложность n*m. При каждом сдвиге количеcтво операций равно m(длина образа), число сдвигов образа получим вычитанием длины образа из длины исходной строки, плюс один (n-m+1)*m. При данном примере получается 72+15=87. Максимальная сложность по видео равна 17*6=102, данную разницу вы игнорируете как не значительную? Или я не правильно считаю?
Ну пожалуйста можно в темном цвете делать презентация смотрю ночью мне пипец как ярко
Этот алгоритм используется в python? Например в str.find() и всех похожим функциям? Кто знает?
@licantrop609
10 ай бұрын
Скорее всего в str.__contains__() используется.
Да ты серьезно? Я не успел ещё посмотреть остальные плейлисты, а тут новое. Круто конечно, но... Что мне делать?
@viktorkomlev5804
3 жыл бұрын
смотри плейлисты по порядку, но когда появляются видео с алгоритмами, залетай туда, знание алгоритмов в работе программиста, важнее, чем умение набирать код
Регулярные выражения?
А можно ли тут обойтись регулярными выражениями? Насколько этот алгоритм будет быстрее работать чем регулярные выражения?
@selfedu_rus
2 жыл бұрын
Если просто найти образец в строке, то подобные алгоритмы будут работать быстрее регулярок. (При условии, что программа делается на С++, а не Python). Если же используете Python, то опять же, лучше брать соответствующие методы строк: count(), index(), find() и т.п. Регулярные - это более изощренный инструмент для тонкой обработки.
Жаль, django закончилось, я только вошел во вкус)
Скажите пожалуйста в какой программе пишите код
@selfedu_rus
4 ай бұрын
PyCharm
пишет не найдено
Можно регулярным выражением сделать
Давай джанго , плиз
Полчаса пролетели за минуту 🙂
Привет друг. Я тебе рекомендую сделать свой курс на stepik что бы прибавить аудиторию
@selfedu_rus
3 жыл бұрын
Спасибо, в ближайших планах )
Реализация на JS: function kmp(text, str) { const N = text.length, M = str.length; let p = new Uint16Array(str.length); for (i = 1, j = 0; 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 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
Мое лицо когда пытаюсь осознать этот алгоритм 6:42
А я ничего не поняла
ничего не понял (((
интересно почему этот вариант не работает 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
7 ай бұрын
а в чем логика здесь вообще? зачем мы каждой отдельной буквой обозначаем номер буквы образца? Зачем здесь инициализация uo, если оно используется один раз? Ну и главный вопрос, если образец будет из, допустим, 99 букв, вы будете каждый номер буквы образца инициализировать отдельно? зачем нам 99 переменных? Ничего не понятно. И читаемость кода ужасная
в чем тут ошибка? #include using namespace std; string find(string s, string a, vector pi){ int i = 0; int j = 0; while(i
так себе понятно... хотя это не удивительно, ведь речь идет об алгоритмах. Самое бесячее, что нельзя задать какой то вопрос в моменте
Матиясевич Советский ученый, а не русский
@selfedu_rus
3 жыл бұрын
Русскую национальность никто не отменял, см. в википедии: ru.wikipedia.org/wiki/Матиясевич,_Юрий_Владимирович
Python - это хорошо, но JS ещё лучше)
@fghinty7623
3 жыл бұрын
а?
@nadyamoscow2461
3 жыл бұрын
JS тут тоже есть. Правда, не знаю, чем оно лучше, чем Python
@fontyfx6843
3 жыл бұрын
Наоборот
@whitepepper742
7 ай бұрын
Опять гонки какой язык лучше🤡Под определенную задачу свой язык
А если сравнивать текст с образцом по букве а и в случае совпадения сравнивать всё?