Примечание. В этом примечании мы используем индексацию с нуля. То есть первый символ строки имеет индекс , а последний символ имеет индекс .
Z-функция строки в позиции — это длина наибольшего префикса подстроки, начинающейся в позиции , который также является префиксом всей строки .
Решите эти внешние задачи (например, из Codeforces) чтобы закрепить материал урока:
Более формально,
Значение в позиции обычно определяется как 0 или иногда как длина строки, в зависимости от соглашения.
Простая реализация проверяет ответ независимо для каждой позиции.
Для каждого индекса мы сравниваем подстроку, начинающуюся в , с префиксом строки, пока не найдём первое несовпадение или не достигнем конца строки.
Это даёт решение за .
Чтобы ускорить вычисление, мы поддерживаем текущий Z-блок.
Z-блок — это отрезок строки, который совпадает с префиксом. Мы храним его границы в двух переменных:
l — левая граница;r — правая граница.В любой момент [l, r) — это самый правый отрезок, совпадающий с префиксом строки.
Изначально:
l = 0r = 0Теперь предположим, что мы хотим вычислить z[i].
Тогда позиция i лежит вне текущего Z-блока.
В этом случае мы вычисляем z[i] наивно, сравнивая символы, начиная с префикса.
Тогда позиция i лежит внутри текущего Z-блока.
В этом случае мы уже знаем, что часть ответа можно переиспользовать. Мы смотрим на соответствующую позицию внутри префикса:
и задаём
Это даёт гарантированно корректную нижнюю оценку. После этого мы продолжаем сравнивать символы наивно, если возможно.
Если отрезок, начинающийся в i, выходит за пределы текущего r, мы обновляем Z-блок.
Суммарная сложность этого алгоритма:
Дан текст длины и образец длины , мы хотим найти все вхождения в .
Мы строим новую строку:
где # — символ-разделитель, который не встречается ни в одной из строк.
Затем мы вычисляем Z-функцию для S.
Для каждой позиции в тексте мы смотрим на:
Если это значение равно , то образец встречается в тексте, начиная с позиции .
Это даёт решение за .
Дана строка длины , найдите кратчайшую строку такую, что является конкатенацией одной или более копий .
Чтобы решить это:
Тогда строку можно сжать до длины .
Это также работает за линейное время .
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);
for (int i = 1, l = 0, r = 0; 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;
}