Тренировочная сессия 14: Z-функция — где строка совпадает сама с собой СЕССИЯ

Что тренируем сегодня

Строки — тема, где наивное решение особенно соблазнительно и особенно быстро упирается в лимит времени. «Проверить, встречается ли этот кусок где-то ещё» на первый взгляд стоит одного вложенного цикла, а на строке длиной $10^6$ такой цикл — это $10^{12}$ операций.

Сегодняшний приём — Z-функция: за один линейный проход она считает для каждой позиции строки, насколько далеко от неё тянется совпадение с началом самой строки. Из этой одной таблицы вытаскиваются ответы на целый класс вопросов: где встречается начало строки, является ли начало одновременно концом, какое наибольшее перекрытие строки с самой собой, где спрятан повтор.

Обе задачи на неё, но спрашивают разное. В первой нужно наибольшее перекрытие строки с собой — чтобы каждое следующее её вхождение обходилось дешевле предыдущего. Во второй условие требует сразу трёх вещей от одного куска: чтобы он был началом, концом и встречался где-то в середине. Обе сводятся к одному и тому же массиву, и разница только в том, какое условие по нему проверяется.

Коридор сегодня ~CF 1600–1700.

---

Теория

Z-функция. Для каждой позиции строки она отвечает на один вопрос: насколько далеко отсюда строка совпадает сама с собой, если приложить её начало к этой позиции.

Определение: для строки s длины n значение z[i] — это длина наибольшего общего начала строки s и её суффикса, начинающегося в позиции i. Иначе говоря, z[i] — насколько далеко от позиции i строка совпадает сама с собой, если приложить её начало к этой позиции. Значение z[0] смысла не имеет и обычно полагается равным n.

Пример: для aabaab получаем z = [6, 1, 0, 3, 1, 0]. В позиции 3 совпадение длины 3 — это второе вхождение начала aab.

Зачем она нужна:

• Найти все вхождения одной строки в другую. Склеиваем образец + разделитель + текст, считаем Z-функцию: позиции, где значение равно длине образца, — это вхождения. Разделитель обязан не встречаться ни в одной из строк.
• Проверить, что префикс длины L является суффиксом. Это ровно условие z[n − L] == L: суффикс, начинающийся в позиции n − L, совпадает с началом строки на всю свою длину.
• Проверить, что префикс длины L встречается где-то ещё. Нужна позиция i ≥ 1 с z[i] ≥ L. Если дополнительно требуется, чтобы вхождение не упиралось в конец строки, добавляется условие i + L ≤ n − 1.

Как считается за линию. Наивно каждое z[i] считалось бы посимвольно, и на строке aaaa…a это дало бы $O(n^2)$. Приём в том, чтобы хранить окно [l, r] — вхождение начала строки, которое заканчивается правее всех среди уже найденных. Если очередная позиция i попадает внутрь этого окна, то часть ответа уже известна: участок от i до r совпадает с участком от i − l, значит z[i] можно сразу инициализировать как min(r − i, z[i − l]) и досчитывать только «хвост» за пределами окна. Правая граница r при этом только растёт, поэтому суммарное число посимвольных сравнений линейно.

Каркас приёма — сама Z-функция целиком, это её канонический вид:

Словарь переводов. Практическая ценность Z-функции в том, что почти любой вопрос про повторы внутри строки переводится в одно условие на массив z. Этот словарь стоит держать под рукой — он и есть настоящий приём, а сама функция лишь инструмент:

Особенно полезна вторая строка таблицы: она превращает довольно мутный вопрос «на сколько символов строка может наложиться сама на себя» в один проход по массиву. Условие i + z[i] == n читается так: совпадение, начавшееся в позиции i, тянется ровно до конца строки — значит суффикс от i совпал с началом целиком.

Почему проход по i начинают с единицы. Значение z[0] по соглашению равно длине строки, и условие i + z[i] == n при i = 0 выполняется всегда. Если не пропустить нулевую позицию, «наибольшим началом, которое является концом» окажется вся строка — формально верно, практически бесполезно, а в задачах вроде сегодняшней первой это приводит к пустому «хвосту» и зацикливанию.

Где приём перестаёт работать. Z-функция отвечает на вопросы про точные совпадения. Как только в условии появляется «с точностью до одной ошибки», «с точностью до перестановки символов» или сравнение по какому-то другому правилу, она перестаёт помогать напрямую — нужны хеши, автоматы или другая техника. Иногда, впрочем, задачу удаётся привести к точному совпадению заменой алфавита: например, если важны не сами значения, а их разности, Z-функцию считают по массиву разностей — и сравнение «с точностью до сдвига» превращается в обычное точное.

С чем путают. Ближайший сосед — префикс-функция. Они близки и взаимозаменяемы, но означают разное: z[i] — совпадение с началом строки от позиции i, а префикс-функция π[i] — длина наибольшего собственного бордера префикса, оканчивающегося в i. Обе решают этот класс задач, но формулы проверок у них разные, и смешивать их нельзя. Второй сосед — полиномиальные хеши: они универсальнее (сравнивают любые два куска за константу), но дают вероятностный ответ и требуют аккуратности с модулем, тогда как Z-функция детерминирована и короче.

Сложность приёма: $O(n)$ по времени и памяти.

---

Задача 1 — CF ~1600 — «Camp Schedule»

Что дано

Даны две двоичные строки s и t. Символы строки s разрешается переставить в любом порядке — количество нулей и единиц при этом должно остаться прежним. Нужно выдать такую перестановку, в которой строка t встречается как подстрока максимальное число раз. Вхождения могут перекрываться. Если оптимальных ответов несколько, подойдёт любой.

Формат ввода:

• Строка 1: двоичная строка s ($1 \le |s| \le 500\,000$).
• Строка 2: двоичная строка t ($1 \le |t| \le 500\,000$).

Формат вывода: одна двоичная строка — переставленная s с максимальным числом вхождений t.

Пример 1:

Ввод:
101101
110

Вывод:
110110

Пример 2:

Ввод:
10010110
100011

Вывод:
01100011

Пример 3:

Ввод:
10
11100

Вывод:
01

Разберём на примере

Возьмём первый пример: s = 101101, то есть два нуля и четыре единицы, и t = 110.

Раз символы можно расставлять как угодно, исходный порядок s не важен вовсе — важен только запас: сколько нулей и сколько единиц у нас на руках. Задача превращается в такую: «строим строку из имеющегося запаса, максимизируя число вхождений t».

Первое вхождение стоит ровно t — один ноль и две единицы, после чего в запасе остаётся один ноль и две единицы. Теперь важный вопрос: сколько стоит второе вхождение?

Наивный ответ — снова весь t. Но вхождения разрешено перекрывать, и это бывает дешевле. Посмотрим на t = 110: заканчивается она на 0, а начинается на 1 — общего у начала и конца нет. Значит перекрытия не будет, и второе вхождение действительно стоит целых три символа: 110110. Запаса ровно хватает, получаем два вхождения — совпадает с эталоном.

А теперь возьмём для контраста t = 1101101. Её начало 1101 совпадает с её же концом. Значит, дописав к 1101101 всего три символа 101, мы получим 1101101101 — и в этой строке уже два вхождения, второе начинается там, где ещё не кончилось первое. Второе вхождение обошлось не в семь символов, а в три.

Отсюда весь алгоритм: сначала выписываем t целиком, а потом дописываем его «хвост» — часть после наибольшего начала, которое одновременно является концом, — столько раз, на сколько хватит запаса. То самое «наибольшее начало, которое одновременно конец», и считает Z-функция.

Осталось разобрать третий пример — там t = 11100 требует трёх единиц, а в запасе всего одна. Ни одного вхождения собрать нельзя, поэтому выводим что угодно из имеющихся символов: 01.

Идея решения

Алгоритм в одну фразу: посчитать наибольшую длину начала t, совпадающего с его концом; выписать t один раз, затем дописывать хвост после этого совпадения, пока хватает нулей и единиц; остаток символов вывести в произвольном порядке.

Почему выгодно максимальное перекрытие. Пусть мы уже выписали строку, оканчивающуюся вхождением t, и хотим получить следующее вхождение как можно дешевле. Новое вхождение начинается где-то внутри или сразу после предыдущего; пусть оно перекрывается с ним на k символов. Тогда эти k символов — одновременно конец предыдущего вхождения и начало нового, то есть k — длина начала t, совпадающего с концом t. Дописать придётся |t| − k символов. Чем больше k, тем дешевле, поэтому берём наибольшее возможное перекрытие.

Почему жадность по количеству корректна. Цена каждого следующего вхождения одна и та же — фиксированный набор символов хвоста. Значит число вхождений, которое мы можем себе позволить, определяется только запасом, а порядок «сначала целиком, потом хвостами» тратит минимум символов на каждое вхождение. Никакая другая расстановка не даст больше: каждое вхождение требует хотя бы |t| − k новых символов, где k — максимальное перекрытие.

Причём тут Z-функция. Нужно найти наибольшее L < |t|, при котором начало длины L совпадает с концом длины L. Через Z-функцию это записывается одной строкой: перебираем позиции i от 1 и берём те, где совпадение тянется ровно до конца строки, то есть i + z[i] = |t|; среди них выбираем наибольшее z[i]. Условие i + z[i] = n означает «суффикс, начинающийся в i, совпадает с началом строки на всю свою длину» — это и есть определение начала, которое одновременно конец.

Про остаток. Символы, которых не хватило на очередной хвост, надо просто вывести — они не могут создать новое вхождение (иначе его можно было бы собрать и раньше), но обязаны присутствовать: по условию состав символов менять нельзя.

Псевдокод

прочитать s, t
нулей = количество '0' в s
единиц = количество '1' в s

z = Z-функция(t)
перекрытие = 0
для i от 1 до |t|-1:
    если i + z[i] == |t|:                     // начало длины z[i] является и концом
        перекрытие = max(перекрытие, z[i])

хвост = t[перекрытие ..]                      // цена каждого следующего вхождения

если нулей >= (нулей в t) и единиц >= (единиц в t):
    вывести t
    вычесть состав t из запаса
    пока хватает символов на хвост:
        вывести хвост
        вычесть состав хвоста из запаса

вывести оставшиеся нули, затем оставшиеся единицы

Код решения

Комментарии по реализации. Ответ может достигать полумиллиона символов, поэтому собирать его конкатенацией в цикле (res = res + tail в Python) нельзя — это квадрат по времени. В Python строки накапливаются в список и склеиваются один раз, в C++ используется += у string, который амортизированно линеен. Проверка «собирается ли хотя бы одно вхождение» обязана стоять до цикла: если её пропустить и сразу начать дописывать хвосты, получится строка, в которой t не встречается ни разу, зато состав символов испорчен. И, наконец, border строго меньше длины t: цикл идёт с i = 1, поэтому вырожденный случай «вся строка совпадает сама с собой» не попадает в перебор — иначе хвост оказался бы пустым и цикл стал бы бесконечным.

Проверка на примерах

Пример 1: s = 101101 (два нуля, четыре единицы), t = 110.

Z-функция для 110: z = [3, 1, 0]. Проверяем условие i + z[i] = 3: при i = 1 получаем 1 + 1 = 2 ≠ 3, при i = 2 — 2 + 0 = 2 ≠ 3. Ни одно не подошло, значит border = 0, хвост — вся строка 110.

Результат: 110110, два вхождения. Наш вывод совпадает с эталоном.

Пример 2: s = 10010110 (четыре нуля, четыре единицы), t = 100011 (три нуля, три единицы).

Z-функция для 100011: z = [6, 0, 0, 0, 1, 1]. Проверяем условие i + z[i] = 6. При i = 4 получаем 4 + 1 = 5 — не подходит: совпадение на позиции 4 обрывается, не дотянув до конца строки. При i = 5 получаем 5 + 1 = 6 — подходит. Значит border = 1: у строки 100011 начало и конец совпадают ровно на одном символе, единице.

Хвост — 00011 (три нуля, две единицы).

Результат: 10001101 — одно вхождение 100011, состав символов сохранён (четыре нуля, четыре единицы). Эталонный ответ 01100011 тоже содержит ровно одно вхождение, а по условию подходит любой оптимальный вариант.

Пример 3: s = 10 (один ноль, одна единица), t = 11100 требует трёх единиц. Проверка перед циклом не проходит, поэтому сразу печатаем остаток: 01.

Наш вывод: 01 — совпадает с эталоном.

Крайние случаи

• t длиннее s. Ни одного вхождения; выводим все символы s в любом порядке. Ловится той же проверкой «хватает ли символов на t».
• t состоит из одинаковых символов (например, 111). Тогда наибольшее совпадение начала и конца равно |t| − 1, хвост — один символ, и каждое следующее вхождение стоит одну единицу. Ответ — все единицы подряд.
• |t| = 1. Хвост совпадает с самим t; вхождений будет столько, сколько нужных символов в запасе.
• Символов ровно на одно вхождение. Цикл дописывания не выполнится ни разу, остаток пуст.
• В s нет ни одного символа нужного вида. Например, s из одних нулей, а t содержит единицу — вхождений нет.
• Максимальный размер ($5 \cdot 10^5$). Проверка на то, что строка собирается за линейное время, а не конкатенацией в цикле.

Типичные ошибки

1. Дописывать t целиком каждый раз. Работает, но даёт меньше вхождений, чем можно: перекрытие бесплатно увеличивает их число.
2. Брать не наибольшее совпадение начала и конца, а любое. Меньшее перекрытие — более длинный хвост — меньше вхождений.
3. Искать перекрытие перебором всех длин. Прямая проверка «начало длины L равно концу длины L» для всех L стоит $O(|t|^2)$ и на полумиллионе символов не проходит.
4. Забыть про остаток символов. Состав выходной строки обязан совпадать с исходным; потерянные символы — это неверный ответ, даже если вхождений максимум.
5. Начинать перебор i с нуля. При i = 0 значение z[0] равно длине строки, условие i + z[i] = n выполняется, и «перекрытие» получится равным всей строке — хвост станет пустым, а цикл бесконечным.
6. Собирать ответ через res += tail в Python. На больших тестах это квадратичное время; нужен список и одна склейка.

Сложность

Время: $O(|s| + |t|)$ — Z-функция линейна, сборка ответа линейна по его длине. Память: $O(|s| + |t|)$ — сама строка ответа и массив Z-функции.

---

Задача 2 — CF ~1700 — «Password»

Что дано

Дана строка s из строчных латинских букв. Нужно найти самую длинную непустую строку t, которая одновременно:

• является началом s (префиксом);
• является концом s (суффиксом);
• встречается где-то внутри s — так, что это вхождение не совпадает ни с началом, ни с концом.

Если такой строки нет, вывести Just a legend.

Формат ввода: одна строка s ($1 \le |s| \le 10^6$).

Формат вывода: искомая строка или Just a legend.

Пример 1:

Ввод:
fixprefixsuffix

Вывод:
fix

Пример 2:

Ввод:
abcdabc

Вывод:
Just a legend

Разберём на примере

Возьмём пример 1: fixprefixsuffix. Выпишем строку по позициям (нумерация с нуля):

Кандидат fix длины 3:

• начало строки — позиции 0–2 ✓;
• конец строки — позиции 12–14 ✓;
• вхождение в середине — позиции 6–8 ✓ (это ни начало, ни конец).

Все три условия выполнены, и более длинного кандидата нет: например, fixp уже не является концом строки. Ответ fix.

Теперь пример 2: abcdabc. Кандидат abc — это и начало (позиции 0–2), и конец (позиции 4–6). Но третьего вхождения нет: внутри строки abc больше нигде не встречается. Более короткие кандидаты не подходят по первым двум условиям: ab концом не является, a тоже. Ответ — Just a legend.

Отсюда видно, что нужно уметь быстро отвечать на два вопроса: «является ли начало длины L концом строки» и «встречается ли начало длины L внутри». Оба ответа даёт одна таблица — Z-функция.

Посчитаем Z-функцию для fixprefixsuffix. Ненулевые значения: z[6] = 3 (вхождение fix в середине), z[12] = 3 (вхождение fix в конце), z[11] = 1 (совпадает только буква f). Условие «начало длины 3 является концом» — это z[15 − 3] = z[12] = 3 ✓. Условие «встречается внутри» — существует позиция i от 1 до 15 − 3 − 1 = 11 со значением не меньше 3; такая позиция есть, это i = 6 ✓.

Идея решения

Алгоритм в одну фразу: посчитать Z-функцию, затем перебрать длины L от наибольшей к наименьшей и вернуть первую, для которой z[n − L] == L (начало является концом) и среди позиций 1 … n − L − 1 найдётся значение не меньше L (есть вхождение в середине).

Почему это работает. Первое условие — прямое следствие определения: z[n − L] равно длине совпадения начала строки с суффиксом, стартующим в позиции n − L; этот суффикс имеет длину ровно L, поэтому равенство z[n − L] = L означает полное совпадение, то есть «начало длины L = конец длины L».

Второе условие: вхождение начала длины L в позиции i — это в точности z[i] ≥ L. Чтобы вхождение не было началом, требуется i ≥ 1; чтобы оно не было концом, требуется, чтобы оно заканчивалось раньше последней позиции, то есть i + L ≤ n − 1, откуда i ≤ n − L − 1. Значит нужно узнать, есть ли среди z[1], …, z[n − L − 1] значение не меньше L, — а для этого достаточно заранее посчитать префиксные максимумы массива z и один раз сравнить.

Перебор длин от большей к меньшей даёт самый длинный подходящий вариант, а суммарная стоимость всего перебора — линейная: одна проверка на длину.

Про «пустую» строку. Длина 0 формально подошла бы под все условия, но по условию строка должна быть непустой — поэтому перебор идёт до L = 1, и если ничего не найдено, печатается Just a legend.

Псевдокод

прочитать s, n = длина(s)

z = Z-функция(s)          // z[0] = n, дальше по алгоритму с окном [l, r]

// префиксные максимумы: best[i] = max(z[1..i])
best[0] = 0
для i от 1 до n-1:
    best[i] = max(best[i-1], z[i])

для L от n-1 вниз до 1:
    i = n - L                       // начало суффикса длины L
    если z[i] == L и i-1 >= 1 и best[i-1] >= L:
        вывести s[0..L-1]
        завершить

вывести "Just a legend"

Код решения

Комментарии по реализации. Проверка i − 1 ≥ 1 нужна для коротких кандидатов: при L = n − 1 позиция i равна 1, и отрезок допустимых вхождений пуст — обращаться к best[0] бессмысленно. Массив префиксных максимумов считается один раз, поэтому весь перебор длин линеен; без него каждая проверка стоила бы прохода по z, и решение стало бы квадратичным на строках вида aaa…a. При длине до $10^6$ важен и ввод: одна строка читается целиком, посимвольное чтение здесь заметно дороже самой Z-функции.

Проверка на примерах

Пример 1: s = fixprefixsuffix, n = 15. Ненулевые значения z: z[6] = 3, z[11] = 1, z[12] = 3.

Наш вывод: fix — совпадает с ожидаемым.

Пример 2: s = abcdabc, n = 7. Ненулевые значения: z[4] = 3.

Ни один кандидат не прошёл обе проверки. Наш вывод: Just a legend — совпадает с ожидаемым.

Крайние случаи

• n = 1. Кандидатов нет (перебор начинается с L = 0), сразу Just a legend.
• Строка из одинаковых букв, например aaaaa. Ответ — aaa: начало, конец и вхождение в середине с позиции 1. Хороший тест на то, что Z-функция посчитана за линию, а не за квадрат.
• aaa. Начало a = конец a, вхождение в середине — позиция 1, длина 1, конец строки — позиция 2. Ответ a.
• aa. Кандидат a является началом и концом, но третьего вхождения нет — Just a legend.
• Строка без повторов, abcde. Ни один префикс не является суффиксом — Just a legend.
• Длина $10^6$. Тест на линейность и на скорость ввода.
• Ответ — почти вся строка. Например, aabaabaa: начало aabaa совпадает с концом, а вхождение в середине искать негде — правильный ответ короче, и проверка best обязана это поймать.

Типичные ошибки

1. Проверять только «префикс равен суффиксу». Тогда abcdabc ошибочно даёт abc; третье вхождение — обязательное условие.
2. Считать вхождением конец строки. Ограничение i ≤ n − L − 1 отсекает именно суффиксное вхождение; без него условие вырождается.
3. Искать максимум z заново для каждой длины. На строке из одинаковых букв это $O(n^2)$; префиксные максимумы решают проблему.
4. Путать Z-функцию с префикс-функцией. Проверка «префикс является суффиксом» у них выглядит по-разному; смешение формул даёт неверные ответы на несимметричных тестах.
5. Наивный подсчёт Z-функции. Без окна [l, r] строка aaa…a даёт квадрат.
6. Забыть про z[0]. Значение n — просто соглашение; включать нулевую позицию в поиск вхождений нельзя, иначе любое начало «встретится в середине» само в себе.

Сложность

Время: $O(n)$ — Z-функция, префиксные максимумы и перебор длин линейны. Память: $O(n)$.

---

Самостоятельная тренировка

Все четыре — на сегодняшний приём: в каждой ответ сводится к вопросу «где строка совпадает сама с собой», то есть к одному условию на массив z.

• Codeforces 1326D1 «Prefix-Suffix Palindrome (Easy version)» (~CF 1500) — из строки нужно составить самый длинный палиндром, взяв её начало и её конец (любой длины, в том числе пустой) и склеив их в таком порядке; в лёгкой версии длина строки позволяет решать за квадрат. Подсказка: сначала «съешьте» максимальный совпадающий начало-конец, а к остатку примените проверку на палиндромность его начала и его конца.
• Codeforces 1537E1 «Erase and Extend (Easy Version)» (~CF 1600) — разрешается удалять последний символ строки и удваивать всю строку; нужно получить лексикографически наименьшую строку заданной длины. Подсказка: ответ полностью определяется тем, какое начало строки взять за «кирпич», а сравнение кирпичей — это сравнение строки с её собственным сдвигом.
• Codeforces 2010C2 «Message Transmission Error (hard version)» (~CF 1700) — принятая строка могла получиться из двух подряд идущих копий одного слова, склеенных с перекрытием (перекрытие должно быть строго короче слова и непустым); нужно определить, так ли это, и восстановить слово. Прямое применение сегодняшней таблицы: «начало является концом» — ровно то условие, которое здесь проверяется.
• Codeforces 471D «MUH and Cube Walls» (~CF 1800) — нужно найти количество вхождений одного профиля высот в другой, причём совпадение считается с точностью до общего сдвига по высоте. Самая интересная в наборе: она показывает приём «свести совпадение с точностью до сдвига к точному» — перейдите к массиву разностей соседних высот, и Z-функция заработает как обычно.

Прорешай их самостоятельно — если застрянешь, разбери с AI-партнёром на codepal.ru: он не даёт готовый ответ, а подводит к решению вопросами.

---

Что дальше

Z-функция — из тех инструментов, которые проще один раз выучить наизусть, чем каждый раз выводить: её код занимает шесть строк, а закрывает целый класс вопросов о повторах внутри строки. Но главное сегодня — не сам код, а словарь переводов из теории. Обе задачи решались одинаково: сформулировать требование условия как условие на массив z, а дальше всё уже написано. Именно этот перевод и стоит тренировать — если он не получается, никакая правильная реализация Z-функции не поможет.

На следующей тренировке уходим в динамику: разберём динамику по префиксу, где кроме позиции приходится помнить ещё одну небольшую величину.