WikiSort.ru - Не сортированное

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

Часто Z-функцию записывают в виде вектора длиной ${\displaystyle \left|S\right|}$ . Например, для строки «abcdabscabcdabia» Z-функция будет такой:

Z(abcdabscabcdabia) = [0, 0, 0, 0, 2, 0, 0, 0, 6, 0, 0, 0, 2, 0, 0, 1].

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

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

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

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

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

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

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

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

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

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

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

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;
}

См. также

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

Ссылки

• Статья на MAXimal::algo
• Задача для проверки

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