Не разорит. Практически тот же самый курс и материал есть на канале у Roman Tsarev (и выложен он еще 6 лет назад). Однако, мне нравится манера Сергея излагать материал.
Сергей, спасибо большое! Очень подробное и понятное объяснение! Каждый момент, который бы мог стать сложным, с Вашей подачей абсолютно понятен. Благодаря Вашим курсам и видеороликам получаю зачеты и пятерки на экзаменах в университете =) Спасибо еще раз)
Класс испытал истинное удовольствие от просмотра видео, четко ясно информативно. Спасибо тебе, так держать, молодец что снимаешь такие познавательные видео
Сергей, вы вылучший! Пол года уже изучаю Python и ML по разным русскоязычным и англоязычным курсам. Как устроюсь на работу обязательно отблагодарю "$ THANKS" )
Этот алгоритм легче понять, если пропустить через дебаггер в пайчарме. Я его перезаписал с более наглядными названиями переменных. Если поставить на 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("образ не найден") ```
Сложно с первого раза понять) сегодня реализовал за O(m*n), надеюсь вскоре получится реализовать за О(m+n)) Сергей, спасибо вам большое, особенно за курс по ООП)
Для целей обучения полезно взять описание алгоритма и пытаться самому реализовать его на Пайтон. И потом проверить, чтобы получился одинаковый результат. Т.к. одно и то же можно реализовать по-разному. Тот же список, к примеру, можно заранее задать с конкретными элементами (нулями, к примеру), а можно формировать в процессе выполнения цикла (pi.append(0)). Можно сделать через цикл for, можно - через while, и т.д.
13:40 не совсем корректно звучит "пи от нуля" и т.д. в данном случае, тут же все таки индексы некоторого списка, а не функция) Огромное спасибо за труд, все очень доходчиво!
а зачем рассматривать суффиксы с последним символом образца на 6:30 и далее? ведь если последний символ образца(допустим P_j) совпал с символом строки, то образец считается найденным. А если P_j не совпал, то важно максимальное совпадение префикса и суффикса в образце БЕЗ последнего символа для выполнения сдвига. В последнем случае, если я правильно понимаю, ещё может получиться равенство P_j следующей букве после полученного макс. префикса (т.е. сдвиг будет на ту же самую букву, которая уже точно известно, что не совпала).
Видео хорошее, только непонятно: зачем вынесли последнее условие из цикла while? Образ "лилила" в конце строки "лилилось лилила" одновременно выдаст и "образ найден" и "образ не найден"
Да, согласен, недосмотрел! Можно поправить вот так: if i == n and j != m: Условие вне цикла, чтобы не выполнять лишние операторы в теле цикла. Исправил программу на github.
Только в английской Википедии и нагуглил упомянание, что Кнут в примечаниях работы "Selected Papers on Design of Algorithms" писал про Матиясевича. И больше ничего. Найти бы ещё какой-то материал, подробнее да убедительнее. Если он первый опубликовал, то где он опубликовал? В той же Википедии ссылка на Кнута и работу Матиясевича 1971 года.
не могу понять логику подсчета количества операций при пошаговом сравнении. если длина массива исходного массива n , а длина образа m , как мы получаем сложность n*m. При каждом сдвиге количеcтво операций равно m(длина образа), число сдвигов образа получим вычитанием длины образа из длины исходной строки, плюс один (n-m+1)*m. При данном примере получается 72+15=87. Максимальная сложность по видео равна 17*6=102, данную разницу вы игнорируете как не значительную? Или я не правильно считаю?
Доброго времени суток) Прошу прощения и ни на что не претендую, просто учусь и стараюсь разобраться. Из того что я на данный момент понял про концепцию большого О - умножение подразумевает под собой вложенный цикл. А в прямом поиске его нет (по крайней мере в версии, которую я попробовал написать). И получается что его сложность в общем случае зависит только от размера источника поиска - О(n). Это может хоть как-то быть правильно? Просто я попробовал замерить скорости у этих алгоритмов и из кучи прогонов только раз смог добиться того чтобы КМП обогнал прямой и то только когда сделал для него все условия (красивые, для больших пропусков, повторения букв и всё такое).
Концепция Big O подразумевает не в общем случае, а "в худшем случае", а при прямом поиске для каждой буквы строки в худшем случае придется проходится по каждой букве образца, отсюда и получается O(m*n)
префиксы формируются на 1-м этапе до поиска образца, затем, на 2-м этапе при несовпадении символов используется сдвиг на вычисленный префикс на 1-м этапе
смотри плейлисты по порядку, но когда появляются видео с алгоритмами, залетай туда, знание алгоритмов в работе программиста, важнее, чем умение набирать код
Если просто найти образец в строке, то подобные алгоритмы будут работать быстрее регулярок. (При условии, что программа делается на С++, а не Python). Если же используете Python, то опять же, лучше брать соответствующие методы строк: count(), index(), find() и т.п. Регулярные - это более изощренный инструмент для тонкой обработки.
интересно почему этот вариант не работает 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
а в чем логика здесь вообще? зачем мы каждой отдельной буквой обозначаем номер буквы образца? Зачем здесь инициализация uo, если оно используется один раз? Ну и главный вопрос, если образец будет из, допустим, 99 букв, вы будете каждый номер буквы образца инициализировать отдельно? зачем нам 99 переменных? Ничего не понятно. И читаемость кода ужасная
Реализация на 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
Сергей, спасибо большое. Вы так разорите товарищей с платных курсов
Не разорит. Практически тот же самый курс и материал есть на канале у Roman Tsarev (и выложен он еще 6 лет назад). Однако, мне нравится манера Сергея излагать материал.
Увидел свежее видео, пошел в плейлист, Сергей такое ощущение что вы прям выкладываете что мне надо, спасибо, хорошо объясняете
Сергей , вашей продуктивности можно позавидовать!
Спасибо за труд! Отличное объяснение
Сергей, спасибо большое! Очень подробное и понятное объяснение! Каждый момент, который бы мог стать сложным, с Вашей подачей абсолютно понятен. Благодаря Вашим курсам и видеороликам получаю зачеты и пятерки на экзаменах в университете =) Спасибо еще раз)
Надеюсь, что дорос до этого плейлиста. Сергей, спасибо!)
Я в шоке с качества объяснения. Очень понятно и интересно. Спасибо огромное!
Спасибо, очень доступно объясняете, прекрасная наглядная презентация, а также большое количество примеров и пояснений. Все в миг стало понятно!
Добрый день! не смотрел пока весь в Flask и Django, но лайк однозначно!!!
Благодаря вам понял тонкий момент КМП, спасибо большое!
Ой супер вообще ))) Надеюсь будет много видео в данной рубрике :))
Очень толково объясняете. Спасибо!
Начал смотреть за пару дней до олимпиады. Круть
Спасибо большое! Наконец-то я поняла этот алгоритм и связь префиксов и суффиксов)
Класс испытал истинное удовольствие от просмотра видео, четко ясно информативно. Спасибо тебе, так держать, молодец что снимаешь такие познавательные видео
Сергей, вы вылучший! Пол года уже изучаю Python и ML по разным русскоязычным и англоязычным курсам.
Как устроюсь на работу обязательно отблагодарю "$ THANKS" )
Устроился?
Тоже интересно
Решил изучать питон, ибо тема интересна и привлекает идея работать в айти
На счет знание алгоритмов это в первую очередь я с вами соглашусь уважаемый
Коммент в поддержку! Лучшее объяснение и отличная подача
Этот алгоритм легче понять, если пропустить через дебаггер в пайчарме. Я его перезаписал с более наглядными названиями переменных. Если поставить на 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("образ не найден")
```
Классный урок, интересная и содержательная подача!
Я до сих пор не понимаю, почему так мало просмотров у тебя на канале
Скоро будет много просмотров, а пока можно поддержать автора спонсорством.
Учеба дело очень энергозатратное)) Мозг обывателя гораздо охотнее поглощает тик-ток))
Ответ прост: очень мало заинтересованных этой темой
Сложно с первого раза понять) сегодня реализовал за O(m*n), надеюсь вскоре получится реализовать за О(m+n)) Сергей, спасибо вам большое, особенно за курс по ООП)
Классный алгоритм, прекрасный в своей простоте. Помню решал схожую задачу, но через хэширование
Очень круто объясняешь! Спасибо за уроки!
гениальный алгоритм).. сигарета потухла давно) перематывал раз 20..)
Для целей обучения полезно взять описание алгоритма и пытаться самому реализовать его на Пайтон. И потом проверить, чтобы получился одинаковый результат.
Т.к. одно и то же можно реализовать по-разному. Тот же список, к примеру, можно заранее задать с конкретными элементами (нулями, к примеру), а можно формировать в процессе выполнения цикла (pi.append(0)).
Можно сделать через цикл for, можно - через while, и т.д.
Сложно, но гениально.
ничего не понял, но так интересно, что поскорее хочется начать изучать )
Вы просто Гений!! Спасибище!!!
Хочется весь плейлист сразу в оперативку себе подгрузить)
лучше в жесткий будет конечно
Как раз сейчас алгоритмы смотрю = ) Спасибо за материал!
13:40 не совсем корректно звучит "пи от нуля" и т.д. в данном случае, тут же все таки индексы некоторого списка, а не функция) Огромное спасибо за труд, все очень доходчиво!
Спасибо за такое классное объяснение 🔥
Почему-то момент j = p[j-1] никто не обсуждает, хотя именно к нему нужно уделить внимание в первую очередь. Не понятно как к нему пришли
Если префикс не подошёл, тогда нужно ее длину уменьшить. Максимально эффективно брать длину максимального префикса для самого префикса.
Красиво) Спасибо Вам большое)
за алгоритмы однозначно лайк
Классно! Жаль, невелик список алгоритмов в плэйлисте.
Спасибо, было полезно
а зачем рассматривать суффиксы с последним символом образца на 6:30 и далее? ведь если последний символ образца(допустим P_j) совпал с символом строки, то образец считается найденным. А если P_j не совпал, то важно максимальное совпадение префикса и суффикса в образце БЕЗ последнего символа для выполнения сдвига.
В последнем случае, если я правильно понимаю, ещё может получиться равенство P_j следующей букве после полученного макс. префикса (т.е. сдвиг будет на ту же самую букву, которая уже точно известно, что не совпала).
Большое спасибо за видео!
Спасибо, очень понятно!
Еще можно на основе хэшей, посчитать хэш строки и хэш того что нужно найти и уже пройтись по строке и посмотреть есть ли одинаковые, сложность O(n)
спасибо за видео!
А регулярные выражения именно этот алгоритм используют?
Видео хорошее, только непонятно: зачем вынесли последнее условие из цикла while? Образ "лилила" в конце строки "лилилось лилила" одновременно выдаст и "образ найден" и "образ не найден"
Да, согласен, недосмотрел! Можно поправить вот так: if i == n and j != m: Условие вне цикла, чтобы не выполнять лишние операторы в теле цикла. Исправил программу на github.
Посмотрел один раз, потом записал конспект, потом решил одну задачку со шпорой, смотрю второй раз. Начал что-то понимать…😮
если уже смотрел алгоритм в питоне, то понимаешь что m=len(a), в видео же, не оговаривается о какой m идет разговор, и почему j=m
Так какой алгоритм лучше: КМП или БМХ ?
Спасибо
Очень помогло !
Интересный видос
Хотелось бы по-больше инфы по алгоритмам
потрясающе
спасибо огромное!
Спасибо
Только в английской Википедии и нагуглил упомянание, что Кнут в примечаниях работы "Selected Papers on Design of Algorithms" писал про Матиясевича. И больше ничего. Найти бы ещё какой-то материал, подробнее да убедительнее. Если он первый опубликовал, то где он опубликовал? В той же Википедии ссылка на Кнута и работу Матиясевича 1971 года.
@@deniskamal подробнее, это когда больше подробностей.
@@deniskamal которые убеждают. Очевидно же.
Интересно в чём и как Вы делаете ваши уроки?
какая сложность будет если решать через оператор in?
я смотрел твой плейлист по flask
как я тут оказался?
Спасибо за ролик, очень понятно! А как вы учили алгоритмы?
Ну пожалуйста можно в темном цвете делать презентация смотрю ночью мне пипец как ярко
Это где применяется ? В каких проектах ?
не могу понять логику подсчета количества операций при пошаговом сравнении. если длина массива исходного массива n , а длина образа m , как мы получаем сложность n*m. При каждом сдвиге количеcтво операций равно m(длина образа), число сдвигов образа получим вычитанием длины образа из длины исходной строки, плюс один (n-m+1)*m. При данном примере получается 72+15=87. Максимальная сложность по видео равна 17*6=102, данную разницу вы игнорируете как не значительную? Или я не правильно считаю?
супер
Доброго времени суток) Прошу прощения и ни на что не претендую, просто учусь и стараюсь разобраться.
Из того что я на данный момент понял про концепцию большого О - умножение подразумевает под собой вложенный цикл. А в прямом поиске его нет (по крайней мере в версии, которую я попробовал написать). И получается что его сложность в общем случае зависит только от размера источника поиска - О(n). Это может хоть как-то быть правильно?
Просто я попробовал замерить скорости у этих алгоритмов и из кучи прогонов только раз смог добиться того чтобы КМП обогнал прямой и то только когда сделал для него все условия (красивые, для больших пропусков, повторения букв и всё такое).
Концепция Big O подразумевает не в общем случае, а "в худшем случае", а при прямом поиске для каждой буквы строки в худшем случае придется проходится по каждой букве образца, отсюда и получается O(m*n)
Ты гений
Этот алгоритм используется в python? Например в str.find() и всех похожим функциям? Кто знает?
Скорее всего в str.__contains__() используется.
Подскажите пожалуйста, зачем всё таки брать п[ j-1 ] при формировании массива п если можно просто поставить 0. Префиксы то всё равно все сначала идут
Это условие если j>0
👍
Мы префикс функцию используем только один раз или после каждого при "прикладывания" образца к тексту?
префиксы формируются на 1-м этапе до поиска образца, затем, на 2-м этапе при несовпадении символов используется сдвиг на вычисленный префикс на 1-м этапе
Сдравстуйте, подскажите пожалуйста как сделать чтобы при запуске PyCharm запускалось главное меню с проектами а не запускался последний проект 🙏
File
Settings
Appearance & Behavior
System Settings
Startup/Shoutdown
Reopen last project
Да ты серьезно? Я не успел ещё посмотреть остальные плейлисты, а тут новое. Круто конечно, но... Что мне делать?
смотри плейлисты по порядку, но когда появляются видео с алгоритмами, залетай туда, знание алгоритмов в работе программиста, важнее, чем умение набирать код
Скажите пожалуйста в какой программе пишите код
PyCharm
Жаль, django закончилось, я только вошел во вкус)
А можно ли тут обойтись регулярными выражениями? Насколько этот алгоритм будет быстрее работать чем регулярные выражения?
Если просто найти образец в строке, то подобные алгоритмы будут работать быстрее регулярок. (При условии, что программа делается на С++, а не Python). Если же используете Python, то опять же, лучше брать соответствующие методы строк: count(), index(), find() и т.п. Регулярные - это более изощренный инструмент для тонкой обработки.
Регулярные выражения?
пишет не найдено
Можно регулярным выражением сделать
А я ничего не поняла
Мое лицо когда пытаюсь осознать этот алгоритм 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
а в чем логика здесь вообще? зачем мы каждой отдельной буквой обозначаем номер буквы образца? Зачем здесь инициализация uo, если оно используется один раз?
Ну и главный вопрос, если образец будет из, допустим, 99 букв, вы будете каждый номер буквы образца инициализировать отдельно? зачем нам 99 переменных?
Ничего не понятно. И читаемость кода ужасная
Привет друг. Я тебе рекомендую сделать свой курс на 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
ничего не понял (((
в чем тут ошибка?
#include
using namespace std;
string find(string s, string a, vector pi){
int i = 0;
int j = 0;
while(i
Матиясевич Советский ученый, а не русский
Русскую национальность никто не отменял, см. в википедии: ru.wikipedia.org/wiki/Матиясевич,_Юрий_Владимирович
Python - это хорошо, но JS ещё лучше)
а?
JS тут тоже есть. Правда, не знаю, чем оно лучше, чем Python
Опять гонки какой язык лучше🤡Под определенную задачу свой язык
А если сравнивать текст с образцом по букве а и в случае совпадения сравнивать всё?
Супер понятно, спасибо!