Алгоритмы обработки строк. Эффективные алгоритмы обработки строк. Построение боров, Z-функций, алгоритм Кнута-Морриса-Пратта

Лабораторная №8

Алгоритмы обработки строк

Цель: Изучение эффективных алгоритмов обработки строк. Построение боров, Z-функций, алгоритм Кнута-Морриса-Пратта.

Задачу решить любым алгоритмом ( кроме тривиального)

Варианты:

1.  Найти в строке заданное слово. (Слово это не подстрока)

2.  Найти в тексте заданное предложение.

3.  Для  заданной  строки определить сколько раз в тексте встречаются все  еe подстроки.

4.  Для заданной строки определить количество различных слов в тексте.

5.  Для заданной строки определить количество подстрок в тексте.

6.  Для заданной строки определить количество раз, которое встречается заданная подстрока в тексте.

7.  Найти в строке заданное слово. (Слово это не подстрока)

8.  Найти в тексте заданное предложение.

9.  Для  заданной  строки определить сколько раз в тексте встречаются все  еe подстроки.

10. Для заданной строки определить количество различных слов в тексте.

11. Для заданной строки определить количество подстрок в тексте.

12. Для заданной строки определить количество раз, которое встречается заданная подстрока в тексте.

Отчет должен содержать: Постановку задачи, графическую схему выбранного алгоритма. Для любой тестовой строки (выбрать самостоятельно) построить бор по словам, по подстрокам, суффиксный автомат и дерево суффиксных ссылок, Z-функцию, префикс функцию.