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