verify/manacher.test.cpp

View this file on GitHub
Last update: 2024-12-28 00:04:13+09:00
Problem: https://judge.yosupo.jp/problem/enumerate_palindromes

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_palindromes"
#include "../Utility/template.hpp"
#include "../String/manacher.hpp"

int main() {
    string s;
    cin >> s;
    manacher ma(s);

    rep(i, 0, s.size()*2-1) {
        if(i%2==0) {
            cout << ma.get(i/2) * 2 - 1 << " ";
        }
        else {
            cout << ma.get(i/2, i/2+1) * 2 << " ";
        }

    }

}

#line 1 "verify/manacher.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_palindromes"
#line 1 "Utility/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)

#define TT template <typename T>
TT using vec = vector<T>;
template <class T1, class T2> bool chmin(T1 &x, T2 y) {
    return x > y ? (x = y, true) : false;
}
template <class T1, class T2> bool chmax(T1 &x, T2 y) {
    return x < y ? (x = y, true) : false;
}
struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} io_setup;

/*
@brief verify用テンプレート
*/
#line 1 "String/manacher.hpp"
struct manacher {
    string s;
    int n, sz;
    vec<int> res;

    manacher(string S) : s(S) {
        n = s.size();
        string t = "";
        rep(i, 0, n) {
            t += s[i];
            if(i != n-1) t += "$";
        }
        sz = t.size();
        res = vec<int>(sz, 0);

        int c = 0;
        rep(i, 0, sz) {
            int l = 2 * c - i;
            if(i + res[l] < c + res[c]) res[i] = res[l];
            else {
                int j = c + res[c] - i;
                while(i - j >= 0 && i + j < sz && t[i-j] == t[i+j]) j++;
                res[i] = j;
                c = i;
            }
        }
    }

    int get(int p) {
        return (res[2 * p] + 1)/2;
    }

    int get(int l, int r) {
        int m = 2 * l + 1;
        return res[m]/2;
    }

};
#line 4 "verify/manacher.test.cpp"

int main() {
    string s;
    cin >> s;
    manacher ma(s);

    rep(i, 0, s.size()*2-1) {
        if(i%2==0) {
            cout << ma.get(i/2) * 2 - 1 << " ";
        }
        else {
            cout << ma.get(i/2, i/2+1) * 2 << " ";
        }

    }

}