verify/yosupo-zalgorithm-z_algorithm.test.cpp

• View this file on GitHub
• Last update: 2025-07-03 00:41:25+09:00
• Problem: https://judge.yosupo.jp/problem/zalgorithm
• Link: View error logs on GitHub Actions

Depends on

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

Code

#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm"

#include <iostream>
#include <string>

#include "../algorithm/String/z_algorithm.hpp"

int main() {
    std::string s;
    std::cin >> s;

    auto &&z = algorithm::z_algorithm(s);

    for(auto elem : z) std::cout << elem << " ";
    std::cout << std::endl;
}

#line 1 "verify/yosupo-zalgorithm-z_algorithm.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm"

#include <iostream>
#include <string>

#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


#line 7 "verify/yosupo-zalgorithm-z_algorithm.test.cpp"

int main() {
    std::string s;
    std::cin >> s;

    auto &&z = algorithm::z_algorithm(s);

    for(auto elem : z) std::cout << elem << " ";
    std::cout << std::endl;
}

Back to top page