Z algorithm（最長共通接頭辞）
(algorithm/String/z_algorithm.hpp)

• View this file on GitHub
• Last update: 2025-07-03 00:41:25+09:00
• Include: #include "algorithm/String/z_algorithm.hpp"
• Link: View error logs on GitHub Actions

概要

配列 $S$ に対して，$S$ と各 $i$ における $S[i:]$ の最長共通接頭辞 (LCP: Longest Common Prefix) の長さを求める．

アルゴリズムの計算量は $\mathcal{O}(\lvert S \rvert)$ となる．

参考文献

1. Pro_ktmr. “【図解】線形時間の文字列アルゴリズム「Z algorithm」をイラストとアニメーションでかみ砕く”. Qiita. https://qiita.com/Pro_ktmr/items/16904c9570aa0953bf05.
2. snuke. “文字列の頭良い感じの線形アルゴリズムたち3”. HatenaBlog. https://snuke.hatenablog.com/entry/2014/12/03/214243.

Verified with

• verify/yosupo-zalgorithm-z_algorithm.test.cpp

Code

#ifndef ALGORITHM_Z_ALGORITHM_HPP
#define ALGORITHM_Z_ALGORITHM_HPP 1

/**
 * @brief Z algorithm（最長共通接頭辞）
 * @docs docs/String/z_algorithm.md
 */

#include <vector>

namespace algorithm {

// 最長共通接頭辞 (LCP: Longest Common Prefix) の長さを求める．
// 引数はSTLのシーケンスコンテナであること．O(|S|).
template <class Sequence>
std::vector<int> z_algorithm(const Sequence &s) {
    const int n = s.size();
    std::vector<int> z(n);  // z[i]:=(sとs[i:]のLCPの長さ).
    z[0] = n;
    int i = 1, j = 0;
    while(i < n) {
        while(i + j < n and s[j] == s[i + j]) j++;
        z[i] = j;
        if(j == 0) {
            i++;
            continue;
        }
        int k = 1;
        while(i + k < n and k + z[k] < j) {
            z[i + k] = z[k];
            k++;
        }
        i += k, j -= k;
    }
    return z;
}

}  // namespace algorithm

#endif

#line 1 "algorithm/String/z_algorithm.hpp"



/**
 * @brief Z algorithm（最長共通接頭辞）
 * @docs docs/String/z_algorithm.md
 */

#include <vector>

namespace algorithm {

// 最長共通接頭辞 (LCP: Longest Common Prefix) の長さを求める．
// 引数はSTLのシーケンスコンテナであること．O(|S|).
template <class Sequence>
std::vector<int> z_algorithm(const Sequence &s) {
    const int n = s.size();
    std::vector<int> z(n);  // z[i]:=(sとs[i:]のLCPの長さ).
    z[0] = n;
    int i = 1, j = 0;
    while(i < n) {
        while(i + j < n and s[j] == s[i + j]) j++;
        z[i] = j;
        if(j == 0) {
            i++;
            continue;
        }
        int k = 1;
        while(i + k < n and k + z[k] < j) {
            z[i + k] = z[k];
            k++;
        }
        i += k, j -= k;
    }
    return z;
}

}  // namespace algorithm

Back to top page