Z-функция

Что такое Z-функция

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

Строка: “abacaba”

Z-функция: [0, 0, 1, 0, 3, 0, 1]

• Z[0] = 0, потому что полный префикс не имеет смысла.
• Z[1] = 0, так как префикс, начинающийся с позиции 1 (“bacaba”), не совпадает с началом строки.
• Z[2] = 1, так как префикс, начинающийся с позиции 2 (“acaba”), совпадает с “a”.
• Z[4] = 3, так как префикс, начинающийся с позиции 4 (“aba”), совпадает с “aba”.

Наивная реализация

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

Алгоритм:

1. Создаем массив Z длиной n (длина строки) и инициализируем его нулями.
2. Для каждой позиции i от 1 до n-1: 3. Проверяем, насколько длинный префикс строки, начиная с i, совпадает с началом строки. 4. Сохраняем длину этого префикса в Z[i].

Код на C++:

#include <iostream>
#include <vector>
#include <string>
 
std::vector<int> naiveZFunction(const std::string &s) {
    int n = s.length();
    std::vector<int> Z(n, 0);
 
    for (int i = 1; i < n; i++) {
        while (i + Z[i] < n && s[Z[i]] == s[i + Z[i]]) {
            Z[i]++;
        }
    }
 
    return Z;
}
 
int main() {
    std::string s = "abacaba";
    std::vector<int> Z = naiveZFunction(s);
 
    for (int z : Z) {
        std::cout << z << " ";
    }
    return 0;
}

Эффективная реализация

Наивный алгоритм имеет временную сложность O(n^2), что не подходит для длинных строк. Существует более эффективный алгоритм с временной сложностью O(n), который использует так называемое “правило зеркала”.

Алгоритм:

1. Создаем массив Z длиной n и инициализируем его нулями.
2. Устанавливаем две переменные L и R, которые обозначают границы правого самого сегмента, совпадающего с префиксом строки.
3. Для каждой позиции i от 1 до n-1: 4. Если i находится за пределами сегмента (i > R), то делаем то же, что и в наивном алгоритме. 5. Если i находится внутри сегмента (i <= R), то используем уже вычисленные значения Z-функции для зеркальной позиции относительно L. 6. Поправляем значение Z[i] с помощью прямого сравнения, если необходимо, и обновляем L и R.

Код на C++:

#include <iostream>
#include <vector>
#include <string>
 
std::vector<int> efficientZFunction(const std::string &s) {
    int n = s.length();
    std::vector<int> Z(n, 0);
    int L = 0, R = 0;
 
    for (int i = 1; i < n; i++) {
        if (i <= R) {
            Z[i] = std::min(R - i + 1, Z[i - L]);
        }
        while (i + Z[i] < n && s[Z[i]] == s[i + Z[i]]) {
            Z[i]++;
        }
        if (i + Z[i] - 1 > R) {
            L = i;
            R = i + Z[i] - 1;
        }
    }
 
    return Z;
}
 
int main() {
    std::string s = "abacaba";
    std::vector<int> Z = efficientZFunction(s);
 
    for (int z : Z) {
        std::cout << z << " ";
    }
    return 0;
}

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