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