⇤ ← Версия 1 от 2013-04-26 14:17:14
1874
Комментарий:
|
1948
|
Удаления помечены так. | Добавления помечены так. |
Строка 9: | Строка 9: |
* (если успеем) Оптимизация многократного поиска многих строк в одной | * (если успеем) [[http://www.chiark.greenend.org.uk/~sgtatham/algorithms/blocksort.html|Оптимизация многократного поиска многих строк в одной]] |
Поиск подстрок в строке
Z-функция и ¶-функция (на примере z-fun.py
- их использование в алгоритмах поиска
(если успеем) Оптимизация многократного поиска многих строк в одной
Домашнее задание
Прочитать про Z-функцию и про ¶-функцию,
- Реализовать поиск подстроки в строке с помощью Z- и ¶-функций. Есть ли различия в эффективности?
- Подсчитать количество различных подстрок в строке
- Представить строку букв в выражения «подстрока*количество_повторений», причём длина этого выражения должна быть минимальная (если строка не может быть представлена в таком виде, ответ — «исходная_строка*1»
…в виде выражения «подстрока1*количество1+…+подстрокаn*количествоn»
- Реализовать поиск множества строк по одной строке
Условные обозначения
— тема по Linux
— тема повышенной сложности
— теоретическое задание
— тема для самостоятельного изучения