Пусть дана строка s длины n. Тогда Z-функция ("зет-функция") от этой строки — это массив длины n, i-ый элемент которого равен наибольшему числу символов, начиная с позиции i, совпадающих с первыми символами строки s.
Иными словами, z[i] — это наибольший общий префикс строки s и её i-го суффикса.
Примечание.…