1948
Комментарий:
|
← Версия 3 от 2013-05-17 15:09:14 ⇥
2135
|
Удаления помечены так. | Добавления помечены так. |
Строка 16: | Строка 16: |
* [[attachment:2013-04-26.count_squeeze.py]] (также решает и первую половину следующей задачи) | |
Строка 19: | Строка 20: |
* [[attachment:2013-04-26.multisearch.py]] |
Поиск подстрок в строке
Z-функция и ¶-функция (на примере z-fun.py
- их использование в алгоритмах поиска
(если успеем) Оптимизация многократного поиска многих строк в одной
Домашнее задание
Прочитать про Z-функцию и про ¶-функцию,
- Реализовать поиск подстроки в строке с помощью Z- и ¶-функций. Есть ли различия в эффективности?
- Подсчитать количество различных подстрок в строке
2013-04-26.count_squeeze.py (также решает и первую половину следующей задачи)
- Представить строку букв в выражения «подстрока*количество_повторений», причём длина этого выражения должна быть минимальная (если строка не может быть представлена в таком виде, ответ — «исходная_строка*1»
…в виде выражения «подстрока1*количество1+…+подстрокаn*количествоn»
- Реализовать поиск множества строк по одной строке
Условные обозначения
— тема по Linux
— тема повышенной сложности
— теоретическое задание
— тема для самостоятельного изучения