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;
}