Cosa (chi) è Z-функция - definizione

Z-фу́нкция от строки ${\displaystyle S}$ — массив ${\displaystyle Z_{1},\dots ,Z_{n}}$, такой что ${\displaystyle Z_{i}}$ равен длине наибольшего общего префикса начинающегося с позиции ${\displaystyle i}$ суффикса строки ${\displaystyle S}$ и самой строки ${\displaystyle S}$. Алгоритм построения был изложен Дэном Гасфилдом в его книге «Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология» в 1997 году на основе публикации Мейна и Лоренца 1984 года о поиске всех тандемных повторов в строке.

Z-функция используется в различных алгоритмах обработки строк. В частности, с её помощью можно быстро решать задачу о поиске вхождения одной строки в другую (поиск по образцу).