Z Algorithm
(library/string/z_algorithm.hpp)

• View this file on GitHub
• Last update: 2026-01-20 20:11:22+09:00
• Include: #include "library/string/z_algorithm.hpp"

Z Algorithm

できること

• 文字列 $S$ が与えられたとき、それぞれの $i$ について $S$ と $S[i, \vert S \vert ]$ の最長共通接頭辞の長さを記録した配列を、線形時間で構築する
• 参考: https://heno239.hatenablog.com/entry/2020/07/07/140651
• 参考: https://ei1333.github.io/library/string/z-algorithm.hpp

aaabaaaab
921034210

計算量

• 空文字列で初期化 ZAlgorithm(): $O(1)$
• 文字列sで初期化 ZAlgorithm(s): $O(N)$
• 文字列の末尾にcを追加 add(c): $O(1)$
• 現在の文字列 $S$ と $S[i, \vert S \vert ]$ の最長共通接頭辞の長さを返す get(k): $O(1)$
• 全ての $i$ についてgetする get(): $O(N)$

使い方

string S = "abacaba";
ZAlgorithm za(S);

// get(k) で S[k..] と S[0..] の共通接頭辞の長さを取得
for (int i = 0; i < (int)S.size(); ++i) za.get(i);
auto all = za.get();
print(all);

Verified with

• Z Algorithmのテスト (tests/string.z_algorithm.test.cpp)

Code

#pragma once
template <typename T = char> struct ZAlgorithm {
  private:
    vector<T> s;
    vector<int> deleted;
    vector<vector<int>> delete_hist;
    vector<int> z;
    queue<int> cur;

  public:
    ZAlgorithm() : delete_hist{{}} {}
    template <typename S> ZAlgorithm(const S &s) : ZAlgorithm() {
        for (auto &c : s) add(c);
    }
    void add(const T &c) {
        s.emplace_back(c);
        delete_hist.emplace_back();
        deleted.emplace_back(0ll);
        z.emplace_back(0ll);
        z[0ll]++;
        int len = (int)s.size();
        if (len == 1ll) return;
        if (s[0ll] == c) {
            cur.emplace(len - 1ll);
        } else {
            deleted[len - 1ll] = 1ll;
        }
        auto set = [&](int t, int len) {
            deleted[t] = 1ll;
            delete_hist[len].emplace_back(t);
            z[t] = len - t - 1ll;
        };
        while (not cur.empty()) {
            int t = cur.front();
            if (deleted[t]) {
                cur.pop();
            } else if (s[len - t - 1ll] == s.back()) {
                break;
            } else {
                set(t, len);
                cur.pop();
            }
        }
        if (not cur.empty()) {
            int t = cur.front();
            for (auto &p : delete_hist[len - t]) {
                set(p + t, len);
            }
        }
    }
    int get(int k) const { return deleted[k] ? z[k] : (int)s.size() - k; }
    int operator[](int k) const { return get(k); }
    vector<int> get() {
        vector<int> ret(s.size());
        for (int i = 0; i < (int)s.size(); i++) {
            ret[i] = get(i);
        }
        return ret;
    }
};

#line 2 "library/string/z_algorithm.hpp"
template <typename T = char> struct ZAlgorithm {
  private:
    vector<T> s;
    vector<int> deleted;
    vector<vector<int>> delete_hist;
    vector<int> z;
    queue<int> cur;

  public:
    ZAlgorithm() : delete_hist{{}} {}
    template <typename S> ZAlgorithm(const S &s) : ZAlgorithm() {
        for (auto &c : s) add(c);
    }
    void add(const T &c) {
        s.emplace_back(c);
        delete_hist.emplace_back();
        deleted.emplace_back(0ll);
        z.emplace_back(0ll);
        z[0ll]++;
        int len = (int)s.size();
        if (len == 1ll) return;
        if (s[0ll] == c) {
            cur.emplace(len - 1ll);
        } else {
            deleted[len - 1ll] = 1ll;
        }
        auto set = [&](int t, int len) {
            deleted[t] = 1ll;
            delete_hist[len].emplace_back(t);
            z[t] = len - t - 1ll;
        };
        while (not cur.empty()) {
            int t = cur.front();
            if (deleted[t]) {
                cur.pop();
            } else if (s[len - t - 1ll] == s.back()) {
                break;
            } else {
                set(t, len);
                cur.pop();
            }
        }
        if (not cur.empty()) {
            int t = cur.front();
            for (auto &p : delete_hist[len - t]) {
                set(p + t, len);
            }
        }
    }
    int get(int k) const { return deleted[k] ? z[k] : (int)s.size() - k; }
    int operator[](int k) const { return get(k); }
    vector<int> get() {
        vector<int> ret(s.size());
        for (int i = 0; i < (int)s.size(); i++) {
            ret[i] = get(i);
        }
        return ret;
    }
};

Back to top page