4. Z алгоритм

Введение: Линейный поиск через префиксные интервалы

Z-алгоритм часто незаслуженно остаётся в тени знаменитых собратьев — 2. Алгоритм Кнута Морриса Пратта и 3. Алгоритм Рабина Карпа, но для опытного бэкенд-разработчика это настоящий скрытый козырь. Он решает задачи поиска подстрок, выявления периодов, быстрого сопоставления префиксов и кластеризации текстов за гарантированное линейное время O(n) с минимальным оверхедом по памяти.

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

В продакшене Z-функция применяется там, где наивный поиск или громоздкие регулярные выражения становятся непреодолимым узким местом (bottleneck):

• Высокопроизводительный парсинг структурированных логов без риска экспоненциального возврата назад (backtracking).
• Дедупликация и нормализация пользовательских сессий.
• Поиск повторяющихся сигнатур в сетевых и телеметрических протоколах.
• Валидация форматов API-токенов.
• Построение компактных индексов для полнотекстовых движков.

Математическое ядро: Z-функция и L-интервалы

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

Формально:
$$z[i] = \max\{k \mid S[0...k-1] == S[i...i+k-1]\}$$
Значение z[0] обычно полагают равным 0 или n в зависимости от контекста задачи.

Ключевая идея алгоритма — поддержание L-интервала [l, r] — самого правого из уже найденных непрерывных отрезков, совпадающего с некоторым префиксом исходной строки S.

Если текущий индекс i оказывается внутри текущего интервала [l, r], мы можем использовать уже вычисленное ранее значение z[i-l], чтобы мгновенно пропустить десятки или сотни посимвольных сравнений!

flowchart TD
    Start["i=1, l=0, r=0"] --> Check{"i <= r?"}
    Check -- Да --> Init["k = i - l<br>z_i = min(r - i + 1, z_k)"]
    Check -- Нет --> Brute["z_i = 0<br>Прямое сравнение символов"]
    Init --> Extend{"z_i продлевается<br>за пределы r?"}
    Extend -- Да --> Update["l = i<br>r = i + z_i - 1"]
    Extend -- Нет --> Next["i++"]
    Brute --> CheckLen{"z_i > 0?"}
    CheckLen -- Да --> Update
    CheckLen -- Нет --> Next
    Update --> Next
    Next --> Check

    classDef default fill:#131d33,stroke:#38bdf8,stroke-width:1.5px,color:#f8fafc;
    classDef branch fill:#1e293b,stroke:#64748b,stroke-width:1px,color:#f8fafc;
    class Check,Extend,CheckLen branch;
  

Благодаря этой изящной геометрии каждый символ строки участвует в успешном сравнении максимум один раз (сдвигая границу r вправо), а в неуспешном сравнении — ровно один раз (немедленно обрывая внутренний цикл). Это обеспечивает строгую амортизированную сложность O(n) без скрытых вычислительных затрат.

Production-реализация на Go 1.21+

Для серверного бэкенда критически важно избегать мусорных аллокаций и работать со срезами байтов напрямую. В Go 1.21+ доступна стандартная встроенная функция min, делающая реализацию лаконичной и быстрой.

package stringsalgo

// ZFunction вычисляет Z-массив для строки s.
// Требует O n памяти и O n времени. Гарантированно линейный проход.
func ZFunction(s []byte) []int {
    n := len(s)
    if n == 0 {
        return nil
    }

    z := make([]int, n)
    l, r := 0, 0

    for i := 1; i < n; i++ {
        // Инициализация через L-интервал
        if i <= r {
            z[i] = min(r-i+1, z[i-l])
        }
        // Наивное расширение совпадения
        for i+z[i] < n && s[z[i]] == s[i+z[i]] {
            z[i]++
        }
        // Обновление правого интервала
        if i+z[i]-1 > r {
            l, r = i, i+z[i]-1
        }
    }
    return z
}

Для классического поиска паттерна P в тексте T применяется объединение P + separator + T. В высоконагруженном коде мы заранее резервируем один буфер нужной емкости, исключая реаллокации:

// FindPattern возвращает индексы вхождения pattern в text.
// Требует uniqueSep, который не встречается ни в pattern, ни в text.
func FindPattern(text, pattern []byte, uniqueSep byte) []int {
    if len(pattern) == 0 || len(text) < len(pattern) {
        return nil
    }

    // Создаём буфер для Z-функции без лишних аллокаций в цикле
    n := len(pattern) + 1 + len(text)
    combined := make([]byte, 0, n)
    combined = append(combined, pattern...)
    combined = append(combined, uniqueSep)
    combined = append(combined, text...)

    z := ZFunction(combined)
    var matches []int

    // Сканируем только часть, соответствующую text
    offset := len(pattern) + 1
    for i := offset; i < len(z); i++ {
        if z[i] == len(pattern) {
            matches = append(matches, i-offset)
        }
    }
    return matches
}

Mechanical Sympathy: кэш, ветвления и рантайм Go

Z-алгоритм — хрестоматийный пример структуры, где математическая строгость идеально согласуется с архитектурой современного микропроцессора.

Пространственная локальность и кэш-линии

Массив z и срез s лежат в абсолютно непрерывных блоках оперативной памяти. Цикл for i := 1; i < n; i++ читает данные строго последовательно. Когда процессор запрашивает байт s[i+z[i]], в 64-байтовую кэш-линию L1-кэша автоматически загружаются следующие десятки байтов. Аппаратный Prefetcher работает с предельной эффективностью, сводя cache miss к статистической погрешности.

Ветвления и предсказатель переходов

Условия i <= r и s[z[i]] == s[i+z[i]] имеют предсказуемый паттерн поведения. В подавляющем большинстве случаев индекс i быстро покидает границы [l, r], и алгоритм переходит к короткой проверке, которая быстро завершается. Предсказатель ветвлений (Branch predictor) угадывает направление с вероятностью >90%, поэтому задержки из-за сброса конвейера (pipeline stall) практически отсутствуют.

Давление на GC и Escape Analysis

Функция ZFunction создает ровно один слайс z в памяти. Механизм Escape Analysis компилятора Go отправляет его в кучу, поскольку срез возвращается вызывающей стороне. Но это одна крупная плоская аллокация размером 8*n байт. Сборщик мусора сканирует ее молниеносно, поскольку срез []int не содержит указателей и не требует обхода графа ссылок. Это радикально дешевле, чем тысячи мелких struct или map элементов.

Применение в бэкенде и сравнение с альтернативами

Поиск минимального периода строки

Z-функция позволяет за линейное время O(n) найти наименьший период p такой, что вся строка S образована многократным повторением префикса S[0..p-1]. Если выполняется условие:

n % (n - z[n]) == 0 && z[n] > 0

то минимальный период равен в точности n - z[n]. Это свойство активно используется при детекции циклических транзакций, сжатии сетевой телеметрии и нормализации метрик в Prometheus/OpenTelemetry.

Сравнение префиксов и кластеризация

При валидации сотен тысяч конфигурационных файлов или правил маршрутизации можно один раз вычислить Z-массив для каждой строки и сгруппировать их по длине совпадающего эталонного префикса. Это дает вычислительную сложность O(N * L) вместо квадратичной O(N² * L) при попарном сравнении, что критично для масштабируемых систем.

Ловушки и вопросы с собеседований

Итог

• Z-алгоритм вычисляет массив длин совпадений суффиксов с префиксом строки за строгое O(n) время и O(n) память.
• Механика L-интервалов позволяет пропускать сравнения, используя уже вычисленные значения, что даёт линейную сложность без рекурсии и сложных префиксных функций.
• В Go реализация идеально дружит с кэш-линиями CPU, минимизирует ветвления и создаёт только одну крупную аллокацию, предсказуемо обрабатываемую сборщиком мусора.
• Ограничения: требует уникального сепаратора при конкатенации, не масштабируется на поиск множества паттернов без перезапуска.
• Production-сценарии: детерминированный поиск без ReDoS, вычисление минимального периода строки, быстрая кластеризация префиксов в конфигурационных движках.

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