Z-функция
Z-функция от строки S - массив Z, каждый элемент которого Z[i] равен длиннейшему префиксу подстроки, начинающейся с позиции i в строке S, который одновременно является и префиксом всей строки Z. Значение Z-функции в нулевой позиции обычно равно или нулю, или длине всей строки.
Сложность
O(|S| ^ 2) или O(|S|).
Префикс-функция от строки
S - массив
P, каждый элемент которого
P[i] равен длиннейшему суффиксу подстроки, начинающейся с позиции
i в строке
S, который одновременно является и суффиксом всей строки
S. Значение
P-функции в нулевой позиции обычно равно или нулю, или длине всей строки.
Сложность
O(|S| ^ 2) или O(|S|).
Попробуйте сами реализовать Z-функцию и префикс-функцию за O(|S| ^ 2).