Чем Z-функция связана с префикс-функцией и как перевести одну в другую?
Понимаю обе функции по отдельности, но не вижу формальной связи. Если у меня уже есть Z-массив, могу ли я получить префикс-функцию без пересчёта, и наоборот? Интересна именно конструктивная связь, а не «они обе про повторы».
2 ответа
Связь конструктивная и работает в обе стороны за O(n).
Из Z в префикс-функцию. Для каждого i с z[i] > 0 блок s[i .. i+z[i]-1] совпадает с префиксом длины z[i]. Значит позиция j = i + z[i] - 1 имеет бордер длины как минимум z[i]. Идём по i и проставляем p[i + z[i] - 1] = max(..., z[i]), затем «протягиваем» значения назад:
vector<int> z_to_prefix(const vector<int>& z) {
int n = z.size();
vector<int> p(n, 0);
for (int i = 1; i < n; ++i)
if (z[i] > 0)
p[i + z[i] - 1] = max(p[i + z[i] - 1], z[i]);
for (int i = n - 1; i >= 1; --i)
if (p[i] > 0)
p[i - 1] = max(p[i - 1], p[i] - 1); // бордер длины L даёт бордер L-1 левее
return p;
}
Из префикс-функции в Z — аналогично: каждый бордер p[i] означает совпадение префикса длины p[i] с суффиксом, заканчивающимся в i, что даёт значение Z в позиции i - p[i] + 1. Тоже O(n).
Итог: обе функции несут одну и ту же информацию о самоповторах строки, просто «с разных концов». Поэтому в задаче можно считать ту, что удобнее писать.
На практике почти никогда не конвертируют одно в другое — проще пересчитать нужную функцию напрямую, это тоже O(n) и без тонкостей с «протягиванием». Конверсия полезна скорее для понимания, что КМП и Z-алгоритм — два лица одной идеи о бордерах/периодах. На контесте берите ту, в чьём коде вы увереннее.