Задания для самостоятельного выполнения
- Сложность:
- Rare
- На любом языке программирования реализуйте:
- наивный алгоритм поиска подстроки в строке,
- алгоритм поиска подстроки в строке, указанный в вашем варианте.
- Сложность:
- Medium
- Напишите программу, решающую задачу по своему варианту.
- Добавьте сбор статистики времени поиска с помощью реализованных алгоритмов.
- Сложность:
- Well-done
- Принимается только самый быстрый алгоритм поиска в своём классе. Для сравнительных тестов использовать словарь Ожегова – найти количество и контекст слова “все”, именно как отдельного слова, а не частей другого слова.
Варианты заданий
КМП. Найти количество и контекст упоминания имён главных героев в книге “Война и мир” и подсчитать их общее количество.
БМХ. Найти в геноме домашней кошки, все места, где встречается самая длинная последовательность “CATCATCAT…CAT”. Формат FASTA.
Рабин. Найти в произвольной книге из симулятора Вавилонской библиотеки, все вхождения неоднобуквенных подстрок своего имени + фамилии в любом регистре, и вывести их с контекстом.
Конечный автомат. Рекурсивно искать все URL-адреса в тексте заданной веб-страницы на указанную глубину. Пример страницы.
Двоичный. Найти количество и время посещений сайта из России в текущий момент времени.
КМП. Найти и удалить из текста заданной веб-страницы все HTML-теги, оставив только текстовое содержимое. Пример страницы.
БМХ. Узнать, находится ли заданный пароль в списке SecLists.
Рабин. Подсчитать вероятность появления в
hexdump /dev/randomзаданной последовательности байтов. Примеры последовательностей:0xF00D, 0xFACE, 0xDEADBEEF, 0xCAFEBABE.Конечный автомат. Найти в репозитории ядра Linux все упоминания заданного фрагмента кода. Например:
struct list_head s_inodes;Аккуратнее с разделителями.Двоичный. Реализовать поиск определений терминов из заданного текста в словаре Ожегова.
КМП. Узнать, содержится ли заданный email в COMB. Пароль
+w/P3PRqQQoJ6g.БМХ. Найти все сообщения с заданным уровнем журналирования в
/var/log/Xorg.0.log.