Z-функция

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

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

Часто Z-функцию записывают в виде вектора длиной \left| S \right|. Например, для строки '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. Изначально L = R = 0.

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

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

Скорость работы[править | править исходный текст]

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

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

Таким образом цикл обрабатывает не более 2\left| S \right| итераций.

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

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

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

Пример реализации на C++[править | править исходный текст]

vector<int> calc_z (const char * s){
	vector<int> z;
	int len = strlen(s);
	z.resize (len);
	z[0] = len;
	int l = 0, r = 0;
	int j;
	for (int i = 1; i < len; i++)
		if (i > r){
			for (j = 0; ((j + i) < len) && (s[i + j] == s[j]) ; j++);
			z[i] = j;
			l = i;
			r = i + j - 1;
		}
		else
			if (z[i - l] < r - i + 1)
				z[i] = z[i - l];
			else{
				for (j = 1; (s[r + j] == s[r - i + j]) && ((j + r) < len); j++);
				z[i] = r - i + j;
				l = i;
				r = r + j - 1;
			}
	return z;
}

Ссылки[править | править исходный текст]

Разбор алгоритма на хабре

Статья на MAXimal::algo

Задача для проверки

См. также[править | править исходный текст]