Определение

Z-функция от строки \(s\) равна массиву \(z\), где \(z[i]\) - максимальная длина \(j\), такая что \(s[0..j - 1] = s[i..i + j - 1]\). Другими словами, \(z[i]\) - длина максимального префикса строки \(s\), совпадающего с префиксом её \(i\)-го суффикса.

Z-функция строки "abacaba"

Значение \(z[0]\) традиционно принимается равным \(0\), поэтому Z-функция от всей строки “abacaba” равна \(\{0, 0, 1, 0, 3, 0, 1\}\).

В определённых случаях префиксы могут перекрываться. Например, Z-функция от строки “aaaa” равна \(\{0, 3, 2, 1\}\).

Тривиальный алгоритм вычисления

Тривиальный алгоритм для вычисления Z-функции имеет сложность \(O(N^2)\) и реализуется следующим образом:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

vector<int> z_function(const string& s) {
    vector<int> z(s.length(), 0);

    for (int i = 1; i < s.length(); i++) {
        for (int j = i; j < s.length(); j++) {
            if (s[j] == s[j - i]) {
                z[i]++;
            } else {
                break;
            }
        }
    }

    return z;
}

Эффективный алгоритм вычисления

Тривиальный алгоритм можно значительно оптимизировать, избавившись от повторных сравнений строк.

Давайте в процессе вычисления Z-функции поддерживать последнее ненулевое найденное значение в виде границ отрезка \([l; r]\), равного соответствующему префиксу. Под “последним” значением понимается отрезок с наибольшим \(r\).

Допустим, мы вычисляем Z-функцию от строки “ababacababa” и находимся на восьмом символе (0-индексация). Тогда последний найденный отрезок будет равен \([6;10]\):

Z-функция строки "ababacababa"

Вместо наивной проверки строки “aba” на равенство префиксу, используем уже рассчитаные значения Z-функции: мы знаем, что \(s[0..5] = s[6..10]\). Значит, \(s[2..5] = s[8..10]\). Но ведь значение \(z[2]\) уже посчитано. Используем его для вычисления \(z[8]\): можно с уверенностью сказать, что \(z[8] \ge \min(z[2], 10 - 8 + 1)\). Заметьте, что мы ограничиваем правую границу отрезка совпадения (\(i + z[i] - 1\)) текущим значением \(r\). Это необходимо, так как мы ничего не знаем о символах правее \(r\).

Таким образом, в качестве начального значения \(z[i]\) можно использовать:

\[z[i] = min(z[i - l], r - i + 1)\]

После чего запускаем наивный алгоритм, пытаясь увеличить \(z[i]\). Это возможно, если правая граница текущего отрезка совпадения превышает \(r\), или если \(i\) не входит в \([l;r]\), и вычислять \(z[i]\) необходимо с нуля.

Если в результате правая граница текущего отрезка (\(i + z[i] - 1\)) превысила \(r\), обновляем значения \(l\) и \(r\).

Сложность такого алгоритма равна \(O(N)\).

Реализация

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

vector<int> z_function(const string& s) {
    vector<int> z(s.length(), 0);

    //начальные значения l и r непринципиальны
    for (int i = 1, l = 0, r = 0; i < s.length(); i++) {
        if (i <= r) {                            //если i входит в уже обработанный отрезок
            z[i] = min(z[i - l], r - i + 1);     //используем предыдущие вычисления
        }

        //иначе начальным значением z[i] остаётся 0

        //пытаемся увеличить z[i] наивным алгоритмом
        while (i + z[i] < s.length()) {
            if (s[i + z[i]] == s[z[i]]) {
                z[i]++;
            } else {
                break;
            }
        }

        //если мы можем увеличить r, делаем это
        if (z[i] > 0 && i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }

    return z;
}

Применение

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#include <bits/stdc++.h>

using namespace std;

vector<int> z_function(const string& s) {
    vector<int> z(s.length(), 0);

    for (int i = 1, l = 0, r = 0; i < s.length(); i++) {
        if (i <= r) {
            z[i] = min(z[i - l], r - i + 1);
        }

        while (i + z[i] < s.length()) {
            if (s[i + z[i]] == s[z[i]]) {
                z[i]++;
            } else {
                break;
            }
        }

        if (z[i] > 0 && i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }

    return z;
}

int main() {
    string s, t;
    cin >> s >> t;

    vector<int> z = z_function(t + '#' + s);

    int t_len = t.length();

    for (int i = 0; i < s.length(); i++) {
        if (z[t_len + 1 + i] == t_len) {
            cout << "s[" << i << ".." << i + t_len - 1 << "] = t" << endl;
        }
    }
}