Z Algorithm
(Library/String/ZAlgorithm.hpp)

• View this file on GitHub
• Last update: 2026-02-08 19:36:48+09:00
• Include: #include "Library/String/ZAlgorithm.hpp"

Z Algorithm

文字列 $S$ について、$S$ の $i$ 文字目以降のみを取り出した部分文字列を $S[i]$ とします。

このとき、$0 \le i \lt \lvert S \rvert$ を満たす整数 $i$ に対して、$S$ と $S[i+1]$ の最長共通接頭辞 (Longest Common Prefix) の長さを $\textrm{O}(\lvert S \rvert)$ 時間で求めることができます。

vector<int> ZAlgorithm(string S)

• 長さ $\lvert S \rvert$ の文字列 $S$ に対して、上記の値を格納した配列 Z を返します。
• Z[i] は、$S$ と $S[i+1]$ の最長共通接頭辞の長さを表します。

制約

• $1 \le \lvert S \rvert \le 10^6$
• $S$ は $1$ バイト文字からなる。

計算量

• $\textrm{O}(\lvert S \rvert)$

---

Depends on

• Library/Common.hpp

Code

#pragma once

#include "../Common.hpp"

vector<int> ZAlgorithm(string S){
    vector<int> Z(S.size(), 0);
    Z[0] = S.size();
    int i = 1, j = 0;
    while(i < S.size()){
        while(i + j < S.size() && S[j] == S[i + j]) ++j;
        Z[i] = j;
        if(j == 0){
            ++i;
            continue;
        }
        int k = 1;
        while(k < j && k + Z[k] < j){
            Z[i + k] = Z[k];
            ++k;
        }
        i += k;
        j -= k;
    }
    return Z;
}

#line 2 "Library/String/ZAlgorithm.hpp"

#line 2 "Library/Common.hpp"

/**
 * @file Common.hpp
 */

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cstdint>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using ll = int64_t;
using ull = uint64_t;

constexpr const ll INF = (1LL << 62) - (3LL << 30) - 1;
#line 4 "Library/String/ZAlgorithm.hpp"

vector<int> ZAlgorithm(string S){
    vector<int> Z(S.size(), 0);
    Z[0] = S.size();
    int i = 1, j = 0;
    while(i < S.size()){
        while(i + j < S.size() && S[j] == S[i + j]) ++j;
        Z[i] = j;
        if(j == 0){
            ++i;
            continue;
        }
        int k = 1;
        while(k < j && k + Z[k] < j){
            Z[i + k] = Z[k];
            ++k;
        }
        i += k;
        j -= k;
    }
    return Z;
}

Back to top page