Изменения

Перейти к: навигация, поиск

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

9 байт добавлено, 21:05, 12 июня 2012
Нет описания правки
Префикс-функция строки <tex>s</tex> {{---}} функция <tex>\pi(i) = \max \limits_{k \in \mathbb N} \{ 0, k | k < i,</tex> <tex>s[1..k] = s[i - k + 1..i], k \in \mathbb N \}</tex>.
==Алгоритм==
Наивный алгоритм вычисляет префикс функцию непосредственно по определению, сравнивая префиксы и суффиксы строк.
304
правки

Навигация