Задания для самостоятельного выполнения

Напишите программу на любом языке программирования, решающую задачу по своему варианту. Помимо указанного алгоритма, в программе нужно реализовать наивный алгоритм поиска. Программа должна собирать статистику времени поиска с помощью реализованных алгоритмов.

Бонусные баллы начисляются за:

Cамый быстрый алгоритм поиска в своём классе. Для сравнительных тестов использовать словарь Ожегова – найти количество и контекст слова “все”, именно как отдельного слова, а не частей другого слова.

Варианты заданий

  1. КМП. Найти количество и контекст упоминания имён главных героев в книге “Война и мир” и подсчитать их общее количество.

  2. БМХ. Найти в геноме домашней кошки, все места, где встречается самая длинная последовательность “CATCATCAT…CAT”. Формат FASTA.

  3. Рабин. Найти в произвольной книге из симулятора Вавилонской библиотеки, все вхождения неоднобуквенных подстрок своего имени + фамилии в любом регистре, и вывести их с контекстом.

  4. Конечный автомат. Рекурсивно искать все URL-адреса в тексте заданной веб-страницы на указанную глубину. Пример страницы.

  5. Двоичный. Найти количество и время посещений сайта из России в текущий момент времени.

  6. КМП. Найти и удалить из текста заданной веб-страницы все HTML-теги, оставив только текстовое содержимое. Пример страницы.

  7. БМХ. Узнать, находится ли заданный пароль в списке SecLists.

  8. Рабин. Подсчитать вероятность появления в hexdump /dev/random заданной последовательности байтов. Примеры последовательностей: 0xF00D, 0xFACE, 0xDEADBEEF, 0xCAFEBABE.

  9. Конечный автомат. Найти в репозитории ядра Linux все упоминания заданного фрагмента кода. Например: struct list_head s_inodes; Аккуратнее с разделителями.

  10. Двоичный. Реализовать поиск определений терминов из заданного текста в словаре Ожегова.

  11. КМП. Узнать, содержится ли заданный email в COMB. Пароль +w/P3PRqQQoJ6g.

  12. БМХ. Найти все сообщения с заданным уровнем журналирования в /var/log/Xorg.0.log.