Z-функция

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Z-фу́нкция от строки S - массив Z, каждый элемент которого Z[i] равен длиннейшему префиксу подстроки, начинающейся с позиции i в строке S, который одновременно является и префиксом всей строки S. Значение Z-функции в нулевой позиции обычно равно или нулю, или длине всей строки; далее будем придерживаться второго варианта.

Часто Z-функцию записывают в виде вектора длиной . Например, для строки 'abcdabscabcdabia' Z-функция будет такой: Z(abcdabscabcdabia)=[16,0,0,0,2,0,0,0,6,0,0,0,2,0,0,1].

Z-функция используется в различных алгоритмах обработки строк. В частности, с её помощью можно быстро решать задачу о поиске вхождения одной строки в другую («поиск по образцу»).

Алгоритм вычисления[править | править вики-текст]

Символы строк нумеруются с 0.

Будем хранить индексы L и R, обозначающие начало и конец префикса с наибольшим найденным на данный момент значением R. Изначально .

Пусть нам известны значения Z-функции для позиций 1..i - 1. Попробуем вычислить значение Z-функции для позиции i. Если , рассмотрим значение Z-функции для позиции . Если , то , так как мы находимся в подстроке, совпадающей с префиксом всей строки. Если же , то необходимо досчитать значение Z[i] простым циклом, перебирающим символы после R, пока не найдется символ, не совпадающий с соответствующим символом из префикса. После этого изменяем, значение L на i и значение R на номер последнего символа, совпавшего с соответствующим символом из префикса.

Если , то считаем значение Z[i] простым циклом, сравнивающим символы подстроки начинающейся с i-того символа и соответствующие символы из префикса. Когда будет найдено несоответствие или будет достигнут конец строки, изменяем значение L на i и значение R на номер последнего символа, совпавшего с соответствующим символом из префикса.

Скорость работы[править | править вики-текст]

Время работы алгоритма, вычисляющего значение Z-функции строки S оценивается в . Докажем это.

Рассмотрим i-тый символ строки. В алгоритме он рассматривается не более двух раз : первый раз, когда попадает в отрезок , и второй раз при вычислении Z[i].

Таким образом цикл обрабатывает не более итераций.

Примеры использования[править | править вики-текст]

1) Z-функцию можно использовать для поиска образца T в строке S, с помощью алгоритма Кнута — Морриса — Пратта, использующего Z-функцию, вместо префикс-функции.

2) Зная Z-функцию строки, можно однозначно восстановить префикс-функцию этой строки, и наоборот.

Пример реализации на C++[править | править вики-текст]

 1 std::vector<std::size_t> calc_z(const std::string& s)
 2 {
 3     const std::size_t len = s.length();
 4 	std::vector<std::size_t> z;
 5     z.resize(len);
 6 	z[0] = len;
 7 	std::size_t l = 0, r = 0;
 8 	std::size_t j;
 9 
10 	for (std::size_t i = 1; i < len; i++)
11     {
12 		if (i > r)
13         {
14 			for (j = 0; ((j + i) < len) && (s[i + j] == s[j]) ; j++)
15             { ; }
16 			z[i] = j;
17 			l = i;
18 			r = (i + j - 1);
19 		}
20 		else
21         {
22 			if (z[i - l] < (r - i + 1))
23             {
24 				z[i] = z[i - l];
25             }
26 			else
27             {
28 				for (j = 1; ((j + r) < len) && (s[r + j] == s[r - i + j]); j++)
29                 { ; }
30 				z[i] = (r - i + j);
31 				l = i;
32 				r = (r + j - 1);
33 			}
34         }
35     }
36 	return z;
37 }

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]