Z-фу́нкция от строки S - массив Z, каждый элемент которого Z[i] равен длиннейшему префиксу подстроки, начинающейся с позиции i в строке S, который одновременно является и префиксом всей строки S. Значение Z-функции в нулевой позиции cчитается равным длине всей строки.
Часто Z-функцию записывают в виде вектора длиной \left| S \right|. Например, для строки 'abcdabscabcdabia' Z-функция будет такой: Z(abcdabscabcdabia)=[16,0,0,0,2,0,0,0,6,0,0,0,2,0,0,1].
Z-функция используется в различных алгоритмах обработки строк. В частности, с её помощью можно быстро решать задачу о поиске вхождения одной...