Z-функция

Определение

Z-функция от строки [math]S[/math] и позиции [math]x[/math], это длина максимального префикса подстроки, начинающейся с позиции [math]x[/math] в строке [math]S[/math], который одновременно является и префиксом всей строки [math]S[/math].

Алгоритм поиска

• Задача

Дана строка [math]S[/math]. Необходимо построить массив [math]Z[/math], такой что [math]Z[i][/math] является префикс функцией данной строки с позиции [math]i[/math]

• Описание алгоритма
• Код алгоритма

int[] z(String p) { int[] ans = new int[p.length()]; ans[0] = 0; int n = p.length(); int left = 0; int right = 0; for (int i = 1; i < n; i++) { if (i > right) { int j = 0; while (i + j < n && p.charAt(i+j) == p.charAt(j)) { j++; } ans[i] = j; left = i; right = i + j - 1; } else { if (ans[i - left] < right - i + 1) { ans[i] = ans[i - left]; } else { int j = 1; while (j + right < n && p.charAt(j+right-i) == p.charAt(right + j)) { j++; } ans[i] = right + j - i; left = i; right = right + j - 1; } } } return ans; }</source>