Что такое Z-функция, чем она отличается от префикс-функции и как её реализовать за O(n)?
Постоянно вижу две почти взаимозаменяемые штуки — префикс-функцию и Z-функцию. В чём концептуальная разница и как пишется Z-функция с пресловутым «z-блоком» [l, r]? Каждый раз путаюсь в обновлении границ.
2 ответа
z[i] — длина наибольшего общего префикса всей строки s и её суффикса, начинающегося в позиции i. То есть «насколько далеко от позиции i строка совпадает сама с собой с начала». z[0] обычно считают равным 0 (или n) по соглашению.
Отличие от префикс-функции: префикс-функция смотрит «префикс = суффикс внутри s[0..i]», а Z — «совпадение суффикса с началом». Они взаимно выводимы, но Z часто нагляднее для задач о вхождениях и периодах.
Идея линейности — поддерживаем самый правый известный совпавший блок [l, r] (отрезок, совпадающий с префиксом). Для нового i внутри блока берём готовое значение z[i-l] как стартовую оценку, потом дотягиваем наивно.
vector<int> z_function(const string& s) {
int n = s.size();
vector<int> z(n, 0);
int l = 0, r = 0;
for (int i = 1; i < n; ++i) {
if (i < r) z[i] = min(r - i, z[i - l]);
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
if (i + z[i] > r) { l = i; r = i + z[i]; }
}
return z;
}
Сложность — O(n) время, O(n) память: каждый наивный шаг while сдвигает r вправо, а r монотонно растёт и ограничен n.
Поиск подстроки через Z: посчитайте Z от pat + '#' + text. Тогда позиция i в текстовой части, где z[i] >= m, — это вхождение. Тот же O(n+m). Часто Z-функцию предпочитают именно из-за прямолинейности этого приёма, тогда как раздельный КМП экономит память. Выбор — вкусовщина, если памяти хватает.