Z-функция и префикс-функция

К разделу

1. Z-функция

1.1. Определение

Пусть дана строка $s$ длины $n$ (индексация с нуля). Z-функцией строки $s$ называется массив $z$ длины $n$, где $z_i$ — длина наибольшей подстроки, начинающейся в позиции $i$, которая одновременно является префиксом строки $s$.

Формально:

$$z_i=max\{k\ge 0:s[0\dots k-1]=s[i\dots i+k-1]\}$$

Значение $z_0$ либо не определяется, либо полагается равным $0$ или $n$ (в разных источниках по-разному; в реализациях чаще всего просто не используется)

Пример:

$$\underbrace{aba}c\overbrace{aba}daba(z_4=3)$$

Здесь подстрока, начинающаяся с позиции 4 (aba), совпадает с префиксом строки длины 3.

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

1.2. Построение за $O(n)$

Наивное вычисление $z_i$ для каждой позиции требует $O(n)$ сравнений на каждую позицию, то есть $O(n^2)$ в сумме. Чтобы получить линейный алгоритм, используются z-блоки

Идея. Будем идти по строке слева направо и поддерживать z-блок — самую правую (по правой границе) из уже найденных подстрок, совпадающих с префиксом. Обозначим его границы $l$ и $r$ (включительно) — это отрезок, на котором мы гарантированно знаем содержимое строки (оно совпадает с началом $s$).

Пусть мы хотим вычислить $z_i$, а все $z_0,\dots ,z_{i-1}$ уже известны. Возможны два случая:

1. $i$ лежит правее z-блока ($i>r$). Тогда о содержимом строки начиная с $i$ нам ничего не известно, и мы вычисляем $z_i$ наивно — посимвольным сравнением $s[i+k]$ с $s[k]$, начиная с $k=0$. После этого, если новый отрезок оказался длиннее текущего z-блока, объявляем его новым z-блоком: $l=i$, $r=i+z_i-1$.

2. $i$ лежит внутри z-блока ($i\le r$). Тогда символы на отрезке $[i,r]$ совпадают с символами префикса $[i-l,r-l]$ — мы это уже знаем, не сравнивая их заново. Значит, можно использовать ранее вычисленное значение $z_{i-l}$:

   • Если $z_{i-l}<r-i+1$ (то есть найденное ранее совпадение не упирается в правую границу блока), то гарантированно $z_i=z_{i-l}$ — увеличить это значение нельзя, потому что символ сразу за пределами блока в исходном совпадении по построению отличался от нужного.
   • Если $z_{i-l}\ge r-i+1$, то мы знаем только то, что $z_i\ge r-i+1$ (совпадение внутри блока гарантировано), а дальше, за пределами блока, нужно дополнительно сравнивать посимвольно, увеличивая значение, пока символы совпадают. После этого при необходимости обновляем z-блок.

vector<int> z_function(string s) {
    int n = (int) 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 + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            z[i]++;
        if (i + z[i] - 1 > r) {
            r = i + z[i] - 1;
            l = i;
        }
    }
    return z;
}

1.3. Доказательство

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

Разобьём работу алгоритма на два вида операций:

• Операции с $O(1)$ временем — вычисление значения по формуле $z_i=min(r-i+1,z_{i-l})$, когда $i\le r$ и результат не требует досчёта. Таких операций ровно $n$ (по одной на итерацию цикла).

• Операции посимвольного сравнения (тело while) — каждое такое сравнение либо заканчивается неудачей (и тогда цикл while для данного $i$ сразу завершается — таких неудачных сравнений не больше одного на итерацию, то есть не больше $n$ суммарно), либо заканчивается успехом и увеличивает $r$ на единицу.

Так как $r$ может увеличиться не более $n$ раз за весь алгоритм (оно ограничено длиной строки и никогда не уменьшается), суммарное число успешных посимвольных сравнений во всех итерациях не превышает $n$.

Таким образом, суммарная работа алгоритма составляет $O(n)$

---

2. Префикс-функция

2.1. Определение

Префикс-функцией строки $s$ длины $n$ называется массив $\pi$, где ${\pi }_i$ — длина наибольшего префикса подстроки $s[0\dots i]$ (то есть первых $i+1$ символов строки), который одновременно является суффиксом этой же подстроки. При этом, сам префикс $s[0\dots i]$ целиком не считается, иначе значение было бы равно $i+1$.

Формально:

$${\pi }_i=max\{k<i+1:s[0\dots k-1]=s[i-k+1\dots i]\}$$

Например, для строки abcdabcabcdabcdab префикс-функция выдаст такой массив

$$[0,0,0,0,1,2,3,1,2,3,4,5,6,7,4,5,6]$$

2.2. Построение за $O(n)$

Алгоритм опирается на уже вычисленные значения ${\pi }_0,\dots ,{\pi }_{i-1}$.

Идея. Пусть $k={\pi }_{i-1}$ — длина наибольшего совпадения префикса с суффиксом для предыдущей позиции. Чтобы вычислить ${\pi }_i$, мы пытаемся «продолжить» это совпадение:

1. Если $s[i]=s[k]$ — совпадение продлевается: $k+=1$, и ${\pi }_i=k$.
2. Если $s[i]\ne s[k]$ — нужно попробовать более короткое совпадение. Мы «откатываемся» по цепочке префикс-функции: $k\leftarrow {\pi }_{k-1}$ (это следующий по длине кандидат — префикс, который сам является суффиксом текущего совпадения), и повторяем сравнение $s[i]$ с $s[k]$. Откат продолжается, пока либо не найдётся совпадение, либо $k$ не станет равным $0$.
3. Если после отката с $k=0$ символы всё ещё не совпадают, ${\pi }_i=0$.

vector<int> prefix_function(string s) {
    int n = (int) s.size();
    vector<int> pi(n, 0);
    int k = 0;
    for (int i = 1; i < n; i++) {
        while (k > 0 && s[i] != s[k])
            k = pi[k - 1];
        if (s[i] == s[k])
            k++;
        pi[i] = k;
    }
    return pi;
}

2.3. Доказательство

Аналогично Z-функции, доказательство начинается с растущей величины — переменной $k$.

Заметим:

• На каждой итерации цикла for переменная $k$ увеличивается не более чем на 1
• Значит, суммарный прирост $k$ за весь алгоритм не превышает $n$, так как всего $n$ итераций внешнего цикла
• Каждая итерация внутреннего цикла while уменьшает $k$ (переход к ${\pi }_{k-1}<k$)
• Так как $k$ не может стать отрицательным, а суммарно оно увеличивалось не более $n$ раз, то и уменьшиться оно может суммарно не более $n$ раз за весь проход

Отсюда суммарное число итераций внутреннего цикла while по всем внешним итерациям не превышает $n$. Значит, общее время работы $O(n)$.

---

3. Алгоритм Кнута–Морриса–Пратта (КМП)

Задача: дан текст $t$ длины $m$ и образец (паттерн) $p$ длины $n$; требуется найти все вхождения $p$ в $t$.

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

Наиболее простой в реализации способ — свести поиск подстроки к вычислению префикс-функции одной составной строки:

$$K=p+\mathrm{\#}+t,$$

где $\mathrm{\#}$ — символ-разделитель, гарантированно не встречающийся ни в $p$, ни в $t$.

Вычисляем префикс-функцию $\pi$ для строки $K$. Так как разделитель не встречается в $p$ и $t$, значение ${\pi }_i$ никогда не может превысить длину $p=n$.

Если на какой-то позиции $i$ выполняется ${\pi }_i=n$, значит, в этой позиции строки $K$ заканчивается вхождение всего образца $p$, а значит, в исходном тексте $t$ вхождение начинается с позиции $i-2n$ (сдвиг на длину $p$ и разделитель).

По определению, ${\pi }_i$ — длина наибольшего блока, совпадающего с началом строки $K$ (то есть с $p$) и заканчивающегося на позиции $i$. Из-за разделителя эта длина не может превзойти $n$. Равенство ${\pi }_i=n$ означает, что весь образец целиком уместился и совпал перед позицией $i$ — то есть найдено полное вхождение.

Сложность: $O(n+m)$ — как по времени, так и по памяти (нужно хранить строку $K$ и массив $\pi$ для неё).

Тот же результат можно получить, обходя текст $t$ указателем и поддерживая переменную $k$ — длину текущего совпадения с началом $p$ — точно так же, как это делает алгоритм построения префикс-функции, но сравнивая символы текста с символами образца, а откат при несовпадении делать по префикс-функции самого образца ${\pi }_p$.

Как только $k$ достигает $n$, зафиксировано вхождение, после чего можно продолжать поиск, откатив $k$ по ${\pi }_p[n-1]$. Асимптотика та же — $O(n+m)$, но без построения дополнительной строки-конкатенации и с $O(n)$ дополнительной памяти вместо $O(n+m)$.

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

---

4. Сравнение с хэш-подходом: детерминированность против простоты

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

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

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

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

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