test/src/string/manacher/enumerate_palindromes.test.cpp

View this file on GitHub
Last update: 2023-07-09 04:04:16+09:00
Problem: https://judge.yosupo.jp/problem/enumerate_palindromes

Depends on

Manacher (library/string/manacher.hpp)

Code

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

#include <iostream>
#include "library/string/manacher.hpp"

int main() {
    std::string s;
    std::cin >> s;
    suisen::Manacher manacher(s, '$');
    for (int i = 1; i < 2 * int(s.size()); ++i) std::cout << manacher[i] << '\n';
    return 0;
}

#line 1 "test/src/string/manacher/enumerate_palindromes.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_palindromes"

#include <iostream>
#line 1 "library/string/manacher.hpp"



#include <vector>

namespace suisen {
    struct Manacher {
        Manacher() = default;
        template <typename Container>
        Manacher(const Container& container, const typename Container::value_type& dummy) : _n(container.size()), _r(2 * _n + 1) {
            std::vector v{ dummy };
            for (const auto& val : container) v.push_back(val), v.push_back(dummy);
            build(v);
        }

        int operator[](int i) const { return _r[i]; }
        int odd_length(int i) const { return _r[2 * i + 1]; }
        int even_length(int i) const { return _r[2 * i]; }
    private:
        int _n;
        std::vector<int> _r;

        template <typename T>
        void build(const std::vector<T>& v) {
            for (int i = 0, j = 0, siz = v.size(); i < siz;) {
                while (i - j >= 0 and i + j < siz and v[i - j] == v[i + j]) ++j;
                _r[i] = j;
                int k = 1;
                while (i - k >= 0 and k + _r[i - k] < j) _r[i + k] = _r[i - k], ++k;
                i += k, j -= k;
            }
            for (int& r : _r) --r;
        }
    };
} // namespace suisen



#line 5 "test/src/string/manacher/enumerate_palindromes.test.cpp"

int main() {
    std::string s;
    std::cin >> s;
    suisen::Manacher manacher(s, '$');
    for (int i = 1; i < 2 * int(s.size()); ++i) std::cout << manacher[i] << '\n';
    return 0;
}