test/zalgo.test.cpp

• View this file on GitHub
• Last update: 2025-06-06 22:43:22+09:00
• Problem: https://judge.yosupo.jp/problem/zalgorithm

Depends on

• Z-Algorithm (C++/string/z-algo.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm"
#include <iostream>
#include "C++/string/z-algo.hpp"
int main() {
    std::string s;
    std::cin >> s;
    const auto res = man::zalg(s);
    for(size_t i = 0; i < s.size(); ++i) {
        std::cout << res[i] << " \n"[i + 1 == s.size()];
    }
}

#line 1 "test/zalgo.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm"
#include <iostream>
#line 2 "C++/string/z-algo.hpp"

#include <vector>
#include <ranges>
namespace man {
inline std::vector<int> zalg(const std::string &s) noexcept {
    const int n = std::ssize(s);
    int j = 0;
    std::vector<int> pre(n);
    for(const auto i: std::views::iota(1, n)) {
        if(i + pre[i - j] < j + pre[j]) {
            pre[i] = pre[i - j];
        } else {
            int k = std::max(0, j + pre[j] - i);
            while(i + k < n && s[k] == s[i + k]) {
                ++k;
            }
            pre[i] = k;
            j = i;
        }
    }
    pre.front() = n;
    return pre;
}
}

/**
 * @brief Z-Algorithm
 */
#line 4 "test/zalgo.test.cpp"
int main() {
    std::string s;
    std::cin >> s;
    const auto res = man::zalg(s);
    for(size_t i = 0; i < s.size(); ++i) {
        std::cout << res[i] << " \n"[i + 1 == s.size()];
    }
}

Back to top page