Z-функция

Z-фу́нкция от строки S - массив Z, каждый элемент которого Z[i] равен длиннейшему префиксу подстроки, начинающейся с позиции i в строке S, который одновременно является и префиксом всей строки S. Значение Z-функции в нулевой позиции cчитается равным длине всей строки.

Часто Z-функцию записывают в виде вектора длиной $\left| S \right|$. Например, для строки 'abcdabscabcdabia' Z-функция будет такой: Z(abcdabscabcdabia)=[16,0,0,0,2,0,0,0,6,0,0,0,2,0,0,1].

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

Алгоритм вычисления

Символы строк нумеруются с 0.

Будем хранить индексы L и R, обозначающие начало и конец префикса с наибольшим найденным на данный момент значением R. Изначально $L = R = 0$.

Пусть нам известны значения Z-функции для позиций 1..i - 1. Попробуем вычислить значение Z-функции для позиции i. Если $i \in [L..R]$, рассмотрим значение Z-функции для позиции $j = i - L$. Если $i + Z[j] \leqslant R$, то $Z[i] = Z[j]$, так как мы находимся в подстроке, совпадающей с префиксом всей строки. Если же $i + Z[j] > R$, то необходимо досчитать значение Z[i] простым циклом, перебирающим символы после R, пока не найдется символ, не совпадающий с соответствующим символом из префикса. После этого изменяем, значение L на i и значение R на номер последнего символа, совпавшего с соответствующим символом из префикса.

Если $i \notin [L..R]$, то считаем значение Z[i] простым циклом, сравнивающим символы подстроки начинающейся с i-того символа и соответствующие символы из префикса. Когда будет найдено несоответствие или будет достигнут конец строки, изменяем значение L на i и значение R на номер последнего символа, совпавшего с соответствующим символом из префикса.

Скорость работы

Время работы алгоритма, вычисляющего значение Z-функции строки S оценивается в $O(\left| S \right|)$. Докажем это.

Рассмотрим i-тый символ строки. В алгоритме он рассматривается не более двух раз : первый раз, когда попадает в отрезок $[L..R]$, и второй раз при вычислении Z[i].

Таким образом цикл обрабатывает не более $2\left| S \right|$ итераций.

Примеры использования

1) Z-функцию можно использовать для поиска образца T в строке S, с помощью алгоритма Кнута — Морриса — Пратта, использующего Z-функцию, вместо префикс-функции.

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

Пример реализации на C++

vector<int> calc_z (const char * s){
        vector<int> z;
        int len = strlen(s);
        z.resize (len);
        z[0] = len;
        int l = 0, r = 0;
        int j;
        for (int i = 1; i < len; i++)
                if (i > r){
                        for (j = 0; (s[i + j] == s[j]) && ((j + i) < len); j++);
                        z[i] = j;
                        l = i;
                        r = i + j - 1;
                }
                else
                        if (z[i - l] < r - i + 1)
                                z[i] = z[i - l];
                        else{
                                for (j = 1; (s[r + j] == s[r - i + j]) && ((j + r) < len); j++);
                                z[i] = r - i + j;
                                l = i;
                                r = r + j - 1;
                        }
        return z;
}

Ссылки

Разбор алгоритма на хабре

Задача для проверки

См. также

• Префикс-функция
• Алгоритм Кнута — Морриса — Пратта