Z-функция

Z-функция $z[i]$ — длина наибольшего общего префикса строки $s$ и её суффикса, начинающегося в позиции $i$.

Для aabxaab: $z = [7, 1, 0, 0, 3, 1, 0]$. Значение $z[0]$ обычно кладут равным $n$ или не определяют вовсе.

Наивно — сравнивать посимвольно: $O(n^2)$. Ускоряется тем же способом, что и префикс-функция: переиспользованием уже посчитанного.

Окно совпадения

Держим полуинтервал $[l, r)$ — тот из уже найденных совпадений с префиксом, который заканчивается правее всех. Формально: среди всех $x < i$ берём тот, где $x + z[x]$ максимально.

Смысл: мы знаем, что $s[l..r)$ совпадает с $s[0..r-l)$. Если новая позиция $i$ попала внутрь этого окна, то её окрестность уже встречалась в начале строки, и часть ответа можно списать оттуда:

$$z[i] \ge \min(r - i,\; z[i - l])$$

Почему минимум, а не просто $z[i-l]$. Совпадение гарантировано только до правой границы окна: что там дальше, мы не знаем и обязаны досравнивать вручную.

vector<int> zFunction(const string& s) {
    int n = s.size();
    vector<int> z(n, 0);
    z[0] = 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;
}

Проверено: на 50 000 случайных строк совпала с прямым посимвольным сравнением.

Почему линия

Каждое успешное сравнение внутри while двигает правую границу $r$ вправо хотя бы на единицу, а $r$ не убывает и не превосходит $n$. Значит, успешных сравнений всего не больше $n$. Неуспешное сравнение в каждой итерации ровно одно.

Измерено:

строка	длина	сравнений	доля от $n$
случайная, алфавит 26	1 000 000	40 006	0,04
случайная, алфавит 2	1 000 000	713 132	0,71
aaaa…	1 000 000	999 999	1,00
строка Фибоначчи	1 346 269	1 346 267	1,00
a^500 b повторами	1 000 000	999 998	1,00

Сравнение с префикс-функцией

Обратите внимание на разницу с таблицей из статьи про префикс-функцию: на aaaa… и на строке Фибоначчи префикс-функция не делает ни одного отката, а z-функция делает ровно $n$ сравнений. Худшие случаи у них разные.

На практике это почти не важно — обе линейны, обе с константой около единицы. Важнее другое:

	префикс-функция	z-функция
что хранит	длину бордера префикса	совпадение суффикса с началом
считается	слева направо, по одному символу	слева направо, но с окном
работает в потоке	да	нет: нужен доступ к началу строки
даёт автомат	да	нет
период строки	сразу, $n - \pi[n-1]$	нужен отдельный проход
длина кода	10 строк	10 строк

Правило: если задача про периодичность, бордеры или поток — префикс-функция. Если про совпадения с началом — z-функция. Если просто найти подстроку — любая, обе сводятся к склейке через разделитель:

string all = t + '\x01' + s;
vector<int> z = zFunction(all);
for (size_t i = t.size() + 1; i < all.size(); i++)
    if (z[i] >= (int)t.size()) { /* вхождение в позиции i - t.size() - 1 */ }

Проверено: на 40 000 пар строк даёт те же позиции, что и поиск через префикс-функцию.

Что считается z-функцией удобнее

Наибольший общий префикс двух суффиксов одной строки — если суффиксы начинаются в $i$ и $0$, это ровно $z[i]$.

Число различных подстрок наращиванием строки по символу: добавив символ в конец, считаем z-функцию перевёрнутой строки и вычитаем максимум.

Сжатие строки: наименьшее $k$, для которого $s$ — повторение префикса длины $k$, находится как наименьший делитель $n$ с $z[k] = n - k$.