Z-функция

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Часто Z-функцию записывают в виде вектора длиной . Например, для строки «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. Изначально .

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

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

Скорость работы[править | править код]

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

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

Таким образом цикл обрабатывает не более итераций.

Примеры использования[править | править код]

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

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

Пример реализации на C++[править | править код]

std::vector<std::size_t> calc_z(const std::string& s) {
    const std::size_t len = s.length();
    std::vector<std::size_t> z;
    z.resize(len);
    z[0] = len;
    std::size_t l = 0, r = 0;
    std::size_t j;

    for (std::size_t i = 1; i < len; ++i) {
        if (i > r) {
            for (j = 0; (j + i < len) && (s[i + j] == s[j]); ++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; (j + r < len) && (s[r + j] == s[r - i + j]); ++j);
                z[i] = r - i + j;
                l = i;
                r = r + j - 1;
            }
        }
    }
    return z;
}

См. также[править | править код]

Ссылки[править | править код]