Поиск подстроки в строке или как мои лекции стали худшими в семестре Этой осенью меня позвали прочитать несколько лекций в одном университете в Германии. Вместо того, чтобы быть скучной говорящей головой с плохим английским и лениво переключать слайды презентации, я решил подготовить красивые странички со всеми нужными материалами. Это дало бы студентам возможность пройти материал в комфортном для них темпе. Мне казалось, что так намного круче: студент может пропускать знакомые куски, может сделать паузу на попить кофе, может читать в удобном темпе и возвращаться к уже прочитанному, отвлекаться на ссылки с дополнительной литературой и так далее. Однако студентам такой формат совершенно не зашёл! Большинство из них даже не открыли материалы, на семинарах задачки они не порешали, домашку завалили, да и на экзамене в основном ерунду писали. Другие преподаватели, читающие лекции на этом курсе, выбрали классический вариант говорящей головы в Зуме и выиграли, а я — провалился. Тем не менее, я считаю, что формат оказался неудачным конкретно в этих обстоятельствах, а не вообще — это были незнакомые мне заранее и, кажется, не очень сильно замотивированные студенты, находящиеся в другой стране и говорящие в основном на неродном английском. Мне же совершенно нескромно понравились подготовленные мной материалы, поэтому я решил поделиться своими конспектами с общественностью. Дарю их тем, кто любит алгоритмы так же, как и я, тем, кто преподаёт алгоритмы студентам и школьникам, а также тем, кто решил их изучить: · часть первая, про поиск подстроки в строки, алгоритмы Бойера–Мура–Хорспула, Кнута–Морриса–Пратта и Two-Way-алгоритм (про него мало кто знает!): https://andgein.ru/courses/strings/ · часть вторая, про поиск сразу многих подстрок в одной строке, алгоритм Ахо–Корасик и суффиксные структуры: https://andgein.ru/courses/manystrings/ В лекциях красивые картинки, AI-сгенерированные песня и подкаст (что? да!), вопросы для самопроверки, хорошо подобранные примеры и запускаемые коды с комментариями. Пользуйтесь!