Z, P функции

Что мы еще не проходили?

• P- функция

• Z- функция

• Префикс-функция

• N-функция

• Суффикс-функция

Дана реализация N- функции. Вставьте пропуск.

Дана та же реализация N функции. Вставьте пропуск.

Дана реализация P-функции. Вставьте пропуск.

Дана реализация P-функции. Вставьте пропуск на место машинки.

Какого применения не имеет Z-функции?

• Поиск подстроки в строке

• Поиск количества различных подстрок в строке

• Нахождение периода строки

• Поиск количества пар подстрок, где одна меньше другой лексикографически

• Поиск максимума

Какова асимптотика у Z-функции? Попробуйте объяснить это.

Какова асимптотика у P-функции? Попробуйте объяснить это.

Каково значение Z-функции для следующеq строки в точке 5(нумерация с 0)
abaccabaz

Чему равна P-функция для следующей строки в точке 5(нумерация с 0)?
abaccabaz

• 0

• 1

• 2

• 3