Поиск подстрок в строке
Z-функция и ¶-функция (на примере z-fun.py
- их использование в алгоритмах поиска
(если успеем) Оптимизация многократного поиска многих строк в одной
Домашнее задание
Прочитать про Z-функцию и про ¶-функцию, - Реализовать поиск подстроки в строке с помощью Z- и ¶-функций. Есть ли различия в эффективности?
- Подсчитать количество различных подстрок в строке
2013-04-26.count_squeeze.py (также решает и первую половину следующей задачи)
- Представить строку букв в выражения «подстрока*количество_повторений», причём длина этого выражения должна быть минимальная (если строка не может быть представлена в таком виде, ответ — «исходная_строка*1»
…в виде выражения «подстрока1*количество1+…+подстрокаn*количествоn»
- Реализовать поиск множества строк по одной строке
Условные обозначения
— тема по Linux - — тема повышенной сложности
- — теоретическое задание
— тема для самостоятельного изучения