Определение

Z-функция от строки равна массиву , где - максимальная длина , такая что . Другими словами, - длина максимального префикса строки , совпадающего с префиксом её -го суффикса.

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

Значение традиционно принимается равным , поэтому Z-функция от всей строки “abacaba” равна .

В определённых случаях префиксы могут перекрываться. Например, Z-функция от строки “aaaa” равна .

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

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

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-функции поддерживать последнее ненулевое найденное значение в виде границ отрезка , равного соответствующему префиксу. Под “последним” значением понимается отрезок с наибольшим .

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

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

Вместо наивной проверки строки “aba” на равенство префиксу, используем уже рассчитаные значения 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
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;
        }
    }
}