Z-функция
Примечание. В этой статье используются индексы, основанные на , то есть первый символ строки имеет индекс , а последний — .
Z-функция строки в позиции — это длина наибольшего префикса подстроки, начинающейся в позиции , который совпадает с префиксом всей строки .
Формально:
Значение обычно принимается равным или по соглашению.
Существует простая реализация со сложностью , где — длина строки.
Для каждой позиции мы увеличиваем , пока символы совпадают.
Будем называть Z-блоком подстроку строки , начинающуюся в позиции и имеющую длину , то есть совпадающую с префиксом строки.
Для алгоритма введём две переменные:
Изначально:
Предположим, что значения уже известны для позиций .
Найдём .
Позиция вне текущего Z-блока.
Сравниваем символы напрямую:
пока они совпадают.
Пусть первый несовпадающий индекс — . Тогда:
Обновляем границы:
Позиция внутри текущего Z-блока.
Рассмотрим симметричную позицию:
Тогда известно:
После расширения обновляем:
Линейная реализация :
Даны строки:
Требуется найти все вхождения в .
Построим строку:
где символ — разделитель, не встречающийся в и .
Вычислим Z-функцию строки .
Для каждой позиции в тексте :
Если:
то в позиции строки начинается вхождение .
Иначе — нет.
Асимптотика:
Дана строка длины .
Найти кратчайшую строку , такую что:
(одна или несколько копий ).
Вычислим Z-функцию строки и переберём все делители числа .
Если выполняется:
то строка имеет период , и её можно сжать до длины .
Берём минимальный такой .
Асимптотика:
vector<int> z_function_slow(const string& s) {
int n = s.size();
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;
}
vector<int> z_function(const string& s) {
int n = s.size();
vector<int> z(n);
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;
}