Z Algorithm
(string/z_algorithm.hpp)

• View this file on GitHub
• Last update: 2026-06-21 02:43:08+09:00
• Include: #include "string/z_algorithm.hpp"

Overview

z_algorithm(sequence) returns the longest common prefix length between the whole sequence and every suffix. It is useful for exact pattern matching, periodicity, borders, and comparing a fixed prefix against all positions.

The function is generic over indexable sequences such as std::string and std::vector<int>.

Function

Function	Description	Complexity
vector<int> z_algorithm(const Sequence& sequence)	Returns z[i] = LCP(sequence, sequence[i..]). For a non-empty sequence, z[0] equals its length.	$O(N)$

An empty sequence returns an empty vector.

Example

#include "string/z_algorithm.hpp"

#include <iostream>
#include <string>

int main() {
    std::string text = "ababa";
    auto z = m1une::string::z_algorithm(text);

    for (int length : z) std::cout << length << " ";
    std::cout << "\n"; // 5 0 3 0 1
}

Required by

• String Algorithms Bundle (string/all.hpp)

Verified with

• verify/string/string_algorithms.test.cpp
• verify/string/yosupo_zalgorithm.test.cpp

Code

#ifndef M1UNE_STRING_Z_ALGORITHM_HPP
#define M1UNE_STRING_Z_ALGORITHM_HPP 1

#include <algorithm>
#include <vector>

namespace m1une {
namespace string {

// Returns z[i] = LCP(sequence, sequence[i..]).
template <class Sequence>
std::vector<int> z_algorithm(const Sequence& sequence) {
    int n = int(sequence.size());
    if (n == 0) return {};

    std::vector<int> z(n);
    z[0] = n;
    int left = 0;
    int right = 0;
    for (int i = 1; i < n; i++) {
        if (i < right) z[i] = std::min(right - i, z[i - left]);
        while (i + z[i] < n && sequence[z[i]] == sequence[i + z[i]]) {
            z[i]++;
        }
        if (right < i + z[i]) {
            left = i;
            right = i + z[i];
        }
    }
    return z;
}

}  // namespace string
}  // namespace m1une

#endif  // M1UNE_STRING_Z_ALGORITHM_HPP

#line 1 "string/z_algorithm.hpp"



#include <algorithm>
#include <vector>

namespace m1une {
namespace string {

// Returns z[i] = LCP(sequence, sequence[i..]).
template <class Sequence>
std::vector<int> z_algorithm(const Sequence& sequence) {
    int n = int(sequence.size());
    if (n == 0) return {};

    std::vector<int> z(n);
    z[0] = n;
    int left = 0;
    int right = 0;
    for (int i = 1; i < n; i++) {
        if (i < right) z[i] = std::min(right - i, z[i - left]);
        while (i + z[i] < n && sequence[z[i]] == sequence[i + z[i]]) {
            z[i]++;
        }
        if (right < i + z[i]) {
            left = i;
            right = i + z[i];
        }
    }
    return z;
}

}  // namespace string
}  // namespace m1une

Back to top page