Z-algorithm
(src/string/string.hpp)

• View this file on GitHub
• Last update: 2026-10-12 20:24:58+09:00
• Include: #include "src/string/string.hpp"

関数	説明	計算量
z_algorithm(s) / z_algorithm(first, last)	各 $i$ について、s と s[i:] の最長共通接頭辞の長さ z[i] を並べた vector<int> (z[0] は s の長さ)	$O(n)$

文字列のほか、vector などの列にも使えます。

auto z = z_algorithm(std::string("aabaab"));  // {6, 1, 0, 3, 1, 0}

パターン p の出現位置を求めるには、区切り文字をはさんで連結した p + '$' + s の Z 配列で、値が p.size() 以上の位置を探します。

Verified with

• test/yosupo/zalgorithm.test.cpp

Code

#pragma once

/**
 * @file string.hpp
 * @brief Z-algorithm
 */

#include <iterator>
#include <vector>

/**
 * @brief Z-algorithm
 * s[0:]とs[i:]のLCPの長さを各iについて求める 全体でO(N)
 *
 * @tparam It 配列のイテレータ
 * @param begin 配列の開始イテレータ
 * @param end 配列の終了イテレータ
 * @return std::vector<int> z
 */
template <typename It>
std::vector<int> z_algorithm(It begin, It end) {
    int n = end - begin;
    if (n == 0) return {};
    std::vector<int> z(n);
    z[0] = n;
    for(int i = 1, j = 0; i < n;) {
        // [0, j)と[i, i + j)が一致している
        while(i + j < n && begin[j] == begin[i + j]) j++;
        z[i] = j;
        int k = 1; // [k,)と[i+k,)はLCPが等しいと確定している
        for(; k < j && k + z[k] < j; k++) {
            z[i + k] = z[k];
        }
        i += k;
        if(j) j -= k;
    }
    return z;
}

/**
 * @brief Z-algorithm
 * s[0:]とs[i:]のLCPの長さを各iについて求める 全体でO(N)
 *
 * @tparam R 配列の型
 * @param s 配列
 * @return std::vector<int> z
 */
template <typename R>
std::vector<int> z_algorithm(const R& s) {
    return z_algorithm(std::begin(s), std::end(s));
}

#line 2 "src/string/string.hpp"

/**
 * @file string.hpp
 * @brief Z-algorithm
 */

#include <iterator>
#include <vector>

/**
 * @brief Z-algorithm
 * s[0:]とs[i:]のLCPの長さを各iについて求める 全体でO(N)
 *
 * @tparam It 配列のイテレータ
 * @param begin 配列の開始イテレータ
 * @param end 配列の終了イテレータ
 * @return std::vector<int> z
 */
template <typename It>
std::vector<int> z_algorithm(It begin, It end) {
    int n = end - begin;
    if (n == 0) return {};
    std::vector<int> z(n);
    z[0] = n;
    for(int i = 1, j = 0; i < n;) {
        // [0, j)と[i, i + j)が一致している
        while(i + j < n && begin[j] == begin[i + j]) j++;
        z[i] = j;
        int k = 1; // [k,)と[i+k,)はLCPが等しいと確定している
        for(; k < j && k + z[k] < j; k++) {
            z[i + k] = z[k];
        }
        i += k;
        if(j) j -= k;
    }
    return z;
}

/**
 * @brief Z-algorithm
 * s[0:]とs[i:]のLCPの長さを各iについて求める 全体でO(N)
 *
 * @tparam R 配列の型
 * @param s 配列
 * @return std::vector<int> z
 */
template <typename R>
std::vector<int> z_algorithm(const R& s) {
    return z_algorithm(std::begin(s), std::end(s));
}

Back to top page