Z Algorithm

library

template <class T>
std::vector<int> z_algorithm(const std::vector<T>& s) {
    int n = int(s.size());
    if (n == 0) return {};
    std::vector<int> z(n);
    z[0] = 0;
    for (int i = 1, j = 0; i < n; i++) {
        int& k = z[i];
        k = (j + z[j] <= i) ? 0 : std::min(j + z[j] - i, z[i - j]);
        while (i + k < n && s[k] == s[i + k]) k++;
        if (j + z[j] < i + z[i]) j = i;
    }
    z[0] = n;
    return z;
}

std::vector<int> z_algorithm(const std::string& s) {
    int n = int(s.size());
    std::vector<int> s2(n);
    for (int i = 0; i < n; i++) {
        s2[i] = s[i];
    }
    return z_algorithm(s2);
}

Z Algorithm 解説

※この記事は ChatGPT によって生成されました。

Z 配列とは何か

長さ $n$ の文字列 $S$ に対して、各位置 $i$ について

と定義します。

ここで $\mathrm{LCP}$ は 最長共通接頭辞（Longest Common Prefix） の長さです。

つまり $Z[i]$ は、

「文字列全体 $S$ と、位置 $i$ から始まる接尾辞との一致の長さ」

を表します。

特に

とするのが一般的です。

具体例

例えば

のとき、

• $Z[1]$ は "aabcaabxaaaz" と "abcaabxaaaz" の LCP → $1$
• $Z[4]$ は "aabcaabxaaaz" と "aabxaaaz" の LCP → $3$

というように求めます。

ナイーブ解法

各 $i$ について愚直に比較すると、

になります。

Z algorithm はこれを

で求めます。

Z-box の考え方

現在までに一致している区間を

とします。

この区間は

を満たします。

これを Z-box と呼びます。

アルゴリズムの核心

位置 $i$ に対して次の2ケースに分かれます。

1. $i \ge r$

Z-box の外なので、通常通り先頭から比較して $Z[i]$ を求めます。

2. $i < r$

Z-box の内部なので、

からスタートできます。

もしそれ以上一致するなら、そこから先を追加で比較します。

なぜ線形時間か？

重要なのは：

• 右端 $r$ は単調増加
• 各文字は高々一度しか「新規比較」されない

したがって全体で

になります。

文字列検索への応用

パターン $P$ とテキスト $T$ に対して

を作り、Z 配列を計算します。

すると

となる位置がマッチ位置です。

周期判定

長さ $n$ の文字列に対して、

となる $i$ が存在すれば、

が周期になります。

KMP との関係

• Z algorithm は「prefix vs suffix」
• KMP は「prefix vs prefix」

どちらも本質は

自己一致情報の再利用

です。

実は

• prefix function
• Z function

は相互変換可能です。

まとめ

• $Z[i] = \mathrm{LCP}(S, S[i:])$
• Z-box によって $O(n)$
• 文字列検索・周期判定・境界列挙などに応用可能
• 競技プログラミングで非常に重要な基礎アルゴリズム

AtCoder や AOJ の文字列問題で 「prefix と suffix の一致長を高速に求めたい」と思ったら、 まず Z algorithm を疑うとよいです。

Z Algorithm 問題集（AtCoder / AOJ）

yosupo judge: Z Algorithm

https://judge.yosupo.jp/problem/zalgorithm

AOJ ALDS1_14_B – String Search

URL https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/all/ALDS1_14_B

概要 文字列 T が文字列 S に出現するすべての開始位置を出力せよ。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string T, P;
    cin >> T >> P;

    string s = P + "$" + T;
    vint z = z_algorithm(s);

    vint ans;
    rep(i, (ll)T.size() - (ll)P.size() + 1) {
        if (z[P.size() + i + 1] == (ll)P.size()) ans.push_back(i);
    }
    for (ll x : ans) cout << x << '\n';
}

ABC430: E - Shift String

URL https://atcoder.jp/contests/abc430/tasks/abc430_e

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    auto cal = []() -> void {
        string A, B;
        cin >> A >> B;

        string S = B + A + A;

        vint z = z_algorithm(S);

        int n = A.size();
        rep(i, n) {
            if (z[n + i] >= n) {
                cout << i << '\n';
                return;
            }
        }
        cout << -1 << '\n';
    };

    int t;
    cin >> t;
    rep(i, t) cal();
}

ABC141 E – Who Says a Pun?

URL https://atcoder.jp/contests/abc141/tasks/abc141_e

概要 同じ部分文字列を重ならないように2回使える最大長を求める。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    string S;
    cin >> N >> S;

    ll ans = 0;
    rep(i, N) {
        vint z = z_algorithm(S.substr(i));
        int n = z.size();
        rep(j, n) {
            chmax(ans, min(j, (ll)z[j]));
        }
    }
    cout << ans << endl;
}

ABC284 F – ABCBAC

URL https://atcoder.jp/contests/abc284/tasks/abc284_f

概要 条件を満たす文字列を構成できるか判定する問題。

ABC257 G – Prefix Concatenation

URL https://atcoder.jp/contests/abc257/tasks/abc257_g

概要 文字列を prefix 一致を利用して分割する。