Z-функция строки и её вычисление

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

Иными словами, — это наибольший общий префикс строки и её -го суффикса.

vector<int> z_function (string s) {

int n = (int) s.length();

vector<int> z (n);

for (int i=1, l=0, r=0; i<n; ++i) {

if (i <= r)

z[i] = min (r-i+1, z[i-l]);

while (i+z[i] < n && s[z[i]] == s[i+z[i]])

++z[i];

if (i+z[i]-1 > r)

l = i, r = i+z[i]-1;

}

return z;

}