Msey
Алгоритмы

Z-функция строки и её вычисление | C++

Добавлен , опубликован
Пусть дана строка s длины n. Тогда Z-функция ("зет-функция") от этой строки — это массив длины n, i-ый элемент которого равен наибольшему числу символов, начиная с позиции i, совпадающих с первыми символами строки s.
Иными словами, z[i] — это наибольший общий префикс строки s и её i-го суффикса.
Примечание. В данной статье, во избежание неопределённости, мы будем считать строку 0-индексированной — т.е. первый символ строки имеет индекс 0, а последний — n-1.
Первый элемент Z-функции, z[0], обычно считают неопределённым. В данной статье мы будем считать, что он равен нулю (хотя ни в алгоритме, ни в приведённой реализации это ничего не меняет).
В данной статье приводится алгоритм вычисления Z-функции за время O(n)

Примеры

Приведём для примера подсчитанную Z-функцию для нескольких строк:
"aaaaa":
z[0] = 0,
z[1] = 4,
z[2] = 3,
z[3] = 2,
z[4] = 1.
"aaabaab":
z[0] = 0,
z[1] = 2,
z[2] = 1,
z[3] = 0,
z[4] = 2,
z[5] = 1,
z[6] = 0.
"abacaba":
z[0] = 0,
z[1] = 0,
z[2] = 1,
z[3] = 0,
z[4] = 3,
z[5] = 0,
z[6] = 1.

Тривиальный алгоритм

Формальное определение можно представить в виде элементарной реализации за O(n^2):
vector<int> z_function_trivial (string s) {
	int n = (int) s.length();
	vector<int> z (n);
	for (int i=1; i<n; ++i)
		while (i + z[i] < n && s[z[i]] == s[i+z[i]])
			++z[i];
	return z;
}
Мы просто для каждой позиции i перебираем ответ для неё z[i], начиная с нуля, и до тех пор, пока мы не обнаружим несовпадение или не дойдём до конца строки.
Разумеется, эта реализация слишком неэффективна, перейдём теперь к построению эффективного алгоритма.

Эффективный алгоритм вычисления Z-функции

Чтобы получить эффективный алгоритм, будем вычислять значения z[i] по очереди — от i=1 до n-1, и при этом постараемся при вычислении очередного значения z[i] максимально использовать уже вычисленные значения.
Назовём для краткости подстроку, совпадающую с префиксом строки s, отрезком совпадения. Например, значение искомой Z-функции z[i] — это длиннейший отрезок совпадения, начинающийся в позиции i (и заканчиваться он будет в позиции i + z[i] - 1).
Для этого будем поддерживать координаты [l;r] самого правого отрезка совпадения, т.е. из всех обнаруженных отрезков будем хранить тот, который оканчивается правее всего. В некотором смысле, индекс r — это такая граница, до которой наша строка уже была просканирована алгоритмом, а всё остальное — пока ещё не известно.
Тогда если текущий индекс, для которого мы хотим посчитать очередное значение Z-функции, — это i, мы имеем один из двух вариантов:
i > r — т.е. текущая позиция лежит за пределами того, что мы уже успели обработать.
Тогда будем искать z[i] тривиальным алгоритмом, т.е. просто пробуя значения z[i]=0, z[i]=1, и т.д. Заметим, что в итоге, если z[i] окажется >0, то мы будем обязаны обновить координаты самого правого отрезка [l;r] — т.к. i + z[i] - 1 гарантированно окажется больше r.
i <= r — т.е. текущая позиция лежит внутри отрезка совпадения [l;r].
Тогда мы можем использовать уже подсчитанные предыдущие значения Z-функции, чтобы проинициализировать значение z[i] не нулём, а каким-то возможно бОльшим числом.
Для этого заметим, что подстроки s[l ... r] и s[0 ... r-l] совпадают. Это означает, что в качестве начального приближения для z[i] можно взять соответствующее ему значение из отрезка s[0 ... r-l], а именно, значение z[i-l].
Однако значение z[i-l] могло оказаться слишком большим: таким, что при применении его к позиции i оно "вылезет" за пределы границы r. Этого допустить нельзя, т.к. про символы правее r мы ничего не знаем, и они могут отличаться от требуемых.
Приведём пример такой ситуации, на примере строки "aaaabaa":
Когда мы дойдём до последней позиции (i=6), текущим самым правым отрезком будет [5;6]. Позиции 6 с учётом этого отрезка будет соответствовать позиция 6-5=1, ответ в которой равен z[1] = 3. Очевидно, что таким значением инициализировать z[6] нельзя, оно совершенно некорректно. Максимум, каким значением мы могли проинициализировать — это 1, поскольку это наибольшее значение, которое не вылазит за пределы отрезка [l;r].
Таким образом, в качестве начального приближения для z[i] безопасно брать только такое выражение:
z0[i] = min (r-i+1, z[i-l]).
Проинициализировав z[i] таким значением z0[i], мы снова дальше действуем тривиальным алгоритмом — потому что после границы r, вообще говоря, могло обнаружиться продолжение отрезка совпадение, предугадать которое одними лишь предыдущими значениями Z-функции мы не могли.
Таким образом, весь алгоритм представляет из себя два случая, которые фактически различаются только начальным значением z[i]: в первом случае оно полагается равным нулю, а во втором — определяется по предыдущим значениям по указанной формуле. После этого обе ветки алгоритма сводятся к выполнению тривиального алгоритма, стартующего сразу с указанного начального значения.
Алгоритм получился весьма простым. Несмотря на то, что при каждом i в нём так или иначе выполняется тривиальный алгоритм — мы достигли существенного прогресса, получив алгоритм, работающий за линейное время. Почему это так, рассмотрим ниже, после того, как приведём реализацию алгоритма.

Реализация

Реализация получается весьма лаконичной:
vector<int> z_function (string s) {
	int n = (int) s.length();
	vector<int> z (n);
	for (int i=1, l=0, r=0; i<n; ++i) {
		if (i <= r)
			z[i] = min (r-i+1, z[i-l]);
		while (i+z[i] < n && s[z[i]] == s[i+z[i]])
			++z[i];
		if (i+z[i]-1 > r)
			l = i,  r = i+z[i]-1;
	}
	return z;
}
Прокомментируем эту реализацию.
Всё решение оформлено в виде функции, которая по строке возвращает массив длины n — вычисленную Z-функцию.
Массив z[] изначально заполняется нулями. Текущий самый правый отрезок совпадения полагается равным [0;0], т.е. заведомо маленький отрезок, в который не попадёт ни одно i.
Внутри цикла по i = 1 ... n-1 мы сначала по описанному выше алгоритму определяем начальное значение z[i] — оно либо останется нулём, либо вычислится на основе приведённой формулы.
После этого выполняется тривиальный алгоритм, который пытается увеличить значение z[i] настолько, насколько это возможно.
В конце выполняется обновление текущего самого правого отрезка совпадения [l;r], если, конечно, это обновление требуется — т.е. если i+z[i]-1 > r.
Весь алгоритм вычисления Z-функции выполняется за линейное время O(n)
23 фев 2021
  • Размещен: 23.02.2021 12:10:58
  • Создан: 23.02.2021 12:10:58
  • Обновлен: 23.02.2021 12:10:58
3 392
`
ОЖИДАНИЕ РЕКЛАМЫ...
Чтобы оставить комментарий, пожалуйста, войдите на сайт.