Z-функция — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Описание алгоритма)
Строка 7: Строка 7:
 
Для работы алгоритма заведём две переменные: <tex>left</tex> и <tex>right</tex> — начало и конец наибольшего префикса строки <tex>S</tex> с максимальным значением <tex>right</tex>. Изначально <tex>left=0</tex> и <tex>right=0</tex>.
 
Для работы алгоритма заведём две переменные: <tex>left</tex> и <tex>right</tex> — начало и конец наибольшего префикса строки <tex>S</tex> с максимальным значением <tex>right</tex>. Изначально <tex>left=0</tex> и <tex>right=0</tex>.
  
Это динамический алгоритм. Пусть нам известны значения Z-функции от <tex>0</tex> до <tex>i-1</tex>. Найдём <tex>Z[i]</tex>.  
+
Пусть нам известны значения Z-функции от <tex>0</tex> до <tex>i-1</tex>. Найдём <tex>Z[i]</tex>.  
 
Есть два случая: <tex>i > right</tex>  и <tex>i \leq right</tex>.
 
Есть два случая: <tex>i > right</tex>  и <tex>i \leq right</tex>.
  
Пусть <tex>i > right</tex>. Тогда просто пробегаемся по строке <tex>S</tex> и сравниваем символы на позициях <tex>S[i+j]</tex> и <tex>S[j]</tex>.
+
===i > right===
 +
просто пробегаемся по строке <tex>S</tex> и сравниваем символы на позициях <tex>S[i+j]</tex> и <tex>S[j]</tex>.
 
Пусть <tex>j</tex> первая позиция в строке <tex>S</tex> для которой не выполняется равенство <tex>S[i+j] == S[j]</tex>, тогда <tex>j</tex> это и Z-функция для позиции <tex>i</tex>. Тогда <tex>left = i, right = i + j - 1</tex>.  
 
Пусть <tex>j</tex> первая позиция в строке <tex>S</tex> для которой не выполняется равенство <tex>S[i+j] == S[j]</tex>, тогда <tex>j</tex> это и Z-функция для позиции <tex>i</tex>. Тогда <tex>left = i, right = i + j - 1</tex>.  
  
Если <tex>i \leq right</tex>, сравним <tex>Z[i - left] + i</tex> и <tex>right</tex>. Если <tex>right</tex> меньше, то надо просто пробежаться по строке начиная с позиции <tex>right</tex> и вычислить значение <tex>Z[i]</tex>.  
+
===i < right + 1===
 +
сравним <tex>Z[i - left] + i</tex> и <tex>right</tex>. Если <tex>right</tex> меньше, то надо просто пробежаться по строке начиная с позиции <tex>right</tex> и вычислить значение <tex>Z[i]</tex>.  
 
Иначе мы уже знаем значение <tex>Z[i]</tex>, так как оно равно значению <tex>Z[i - left]</tex>.
 
Иначе мы уже знаем значение <tex>Z[i]</tex>, так как оно равно значению <tex>Z[i - left]</tex>.
 
[[Файл:z-f.png]]
 
[[Файл:z-f.png]]

Версия 01:17, 16 апреля 2012

Определение

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]

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

Для работы алгоритма заведём две переменные: [math]left[/math] и [math]right[/math] — начало и конец наибольшего префикса строки [math]S[/math] с максимальным значением [math]right[/math]. Изначально [math]left=0[/math] и [math]right=0[/math].

Пусть нам известны значения Z-функции от [math]0[/math] до [math]i-1[/math]. Найдём [math]Z[i][/math]. Есть два случая: [math]i \gt right[/math] и [math]i \leq right[/math].

i > right

просто пробегаемся по строке [math]S[/math] и сравниваем символы на позициях [math]S[i+j][/math] и [math]S[j][/math]. Пусть [math]j[/math] первая позиция в строке [math]S[/math] для которой не выполняется равенство [math]S[i+j] == S[j][/math], тогда [math]j[/math] это и Z-функция для позиции [math]i[/math]. Тогда [math]left = i, right = i + j - 1[/math].

i < right + 1

сравним [math]Z[i - left] + i[/math] и [math]right[/math]. Если [math]right[/math] меньше, то надо просто пробежаться по строке начиная с позиции [math]right[/math] и вычислить значение [math]Z[i][/math]. Иначе мы уже знаем значение [math]Z[i][/math], так как оно равно значению [math]Z[i - left][/math]. Z-f.png

Время работы алгоритма

Этот алгоритм работает за [math]O(\lvert S\rvert)[/math], так как каждая позиция пробегается не более двух раз: при попадании в диапазон от [math]left[/math] до [math]right[/math] и при высчитывании Z-функции простым циклом.

Код алгоритма

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