検証済み · 最終更新 2026-07-24 · GitHub

Z algorithm

lib/string/z_algorithm.hpp

概要

Z[i] := S[i:Z[i]] == S[0:Z[i]-i]

インクルード

#include "string/z_algorithm.hpp"

関数

名前	説明
`z_algorithm`	Z algorithm

検証

test/yosupo/string/zalgorithm.test.cpp

このヘッダを使うライブラリ（1）

文字列ユーティリティ lib/string/misc.hpp

検証プログラム（5）

test/aoj/dpl/longest_increasing_subsequence.test.cpp test/aoj/dpl/longest_increasing_subsequence.test.cpp
test/aoj/joi/rle.test.cpp test/aoj/joi/rle.test.cpp
test/yosupo/other/longest_increasing_subsequence.test.cpp test/yosupo/other/longest_increasing_subsequence.test.cpp
test/yosupo/string/zalgorithm.test.cpp test/yosupo/string/zalgorithm.test.cpp
test/yukicoder/0273.test.cpp test/yukicoder/0273.test.cpp

実装

#pragma once
#include <vector>

/// @brief Z algorithm
/// @details Z[i] := S[i:Z[i]] == S[0:Z[i]-i]
/// @see https://snuke.hatenablog.com/entry/2014/12/03/214243
/// @complexity $O(n)$
template <class Container>
std::vector<int> z_algorithm(const Container &s) {
    int n = s.size();
    std::vector<int> res(n);
    res[0] = n;
    int i = 1, j = 0;
    while (i < n) {
        while (i + j < n && s[j] == s[i + j]) ++j;
        res[i] = j;
        if (!j) {
            ++i;
            continue;
        }
        int k = 1;
        while (i + k < n && k + res[k] < j) res[i + k] = res[k], ++k;
        i += k, j -= k;
    }
    return res;
}

bundled

#line 2 "lib/string/z_algorithm.hpp"
#include <vector>

/// @brief Z algorithm
/// @details Z[i] := S[i:Z[i]] == S[0:Z[i]-i]
/// @see https://snuke.hatenablog.com/entry/2014/12/03/214243
/// @complexity $O(n)$
template <class Container>
std::vector<int> z_algorithm(const Container &s) {
    int n = s.size();
    std::vector<int> res(n);
    res[0] = n;
    int i = 1, j = 0;
    while (i < n) {
        while (i + j < n && s[j] == s[i + j]) ++j;
        res[i] = j;
        if (!j) {
            ++i;
            continue;
        }
        int k = 1;
        while (i + k < n && k + res[k] < j) res[i + k] = res[k], ++k;
        i += k, j -= k;
    }
    return res;
}