test/z_algorithm.test.cpp

View this file on GitHub
Last update: 2021-12-17 09:20:39+09:00
Problem: https://judge.yosupo.jp/problem/zalgorithm

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm"
#include "../algorithm/z_algorithm.cpp"
#include "../utility/rep.cpp"
#include <iostream>
#include <string>

int main() {
    std::string s;
    std::cin >> s;
    const auto a = z_algorithm(s);
    for (const auto i : rep(0, s.size())) {
        std::cout << a[i] << " \n"[i + 1 == s.size()];
    }
    return 0;
}

#line 1 "test/z_algorithm.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm"
#line 2 "algorithm/z_algorithm.cpp"
#include <vector>

template <class Cont> std::vector<int> z_algorithm(const Cont& c) {
    const int size = c.size();
    std::vector<int> ret(size);
    ret[0] = size;
    int i = 1, j = 0;
    while (i < size) {
        while (i + j < size && c[i + j] == c[j]) j += 1;
        ret[i] = j;
        if (j == 0) {
            i += 1;
            continue;
        }
        int k = 1;
        while (i + k < size && k + ret[k] < j) {
            ret[i + k] = ret[k];
            k += 1;
        }
        i += k;
        j -= k;
    }
    return ret;
}
#line 2 "utility/rep.cpp"
#include <algorithm>

class Range {
    struct Iter {
        int itr;
        constexpr Iter(const int pos) noexcept : itr(pos) {}
        constexpr void operator++() noexcept { ++itr; }
        constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; }
        constexpr int operator*() const noexcept { return itr; }
    };
    const Iter first, last;

  public:
    explicit constexpr Range(const int first, const int last) noexcept : first(first), last(std::max(first, last)) {}
    constexpr Iter begin() const noexcept { return first; }
    constexpr Iter end() const noexcept { return last; }
};

constexpr Range rep(const int l, const int r) noexcept { return Range(l, r); }
constexpr Range rep(const int n) noexcept { return Range(0, n); }
#line 4 "test/z_algorithm.test.cpp"
#include <iostream>
#include <string>

int main() {
    std::string s;
    std::cin >> s;
    const auto a = z_algorithm(s);
    for (const auto i : rep(0, s.size())) {
        std::cout << a[i] << " \n"[i + 1 == s.size()];
    }
    return 0;
}