test/yosupo/string/enumerate_palindromes_rolling_hash.test.cpp

View this file on GitHub
Last update: 2025-12-19 22:22:43+07:00
Problem: https://judge.yosupo.jp/problem/enumerate_palindromes

Depends on

Code

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

#include <bits/stdc++.h>
using namespace std;

#include "ds/disjoint_sparse_table.hpp"
#include "ds/rolling_hash_static.hpp"
#include "other/types.hpp"

struct Monoid {
    using hasher = RollingHashStatic<>;
    using T = array<u64, 3>;
    static T id() { return {}; }
    static T op(const T &l, const T &r) {
        return {
            hasher::concat(l[0], r[0], (i32)r[2]),
            hasher::concat(r[1], l[1], (i32)l[2]),
            l[2] + r[2],
        };
    }
};

template<class F, class I = i32> void binary_search(I &l, I &r, F &&pred) {
    while (r - l > 1) {
        I m = l + (r - l) / 2;
        (pred(m) ? l : r) = m;
    }
}

void solve() {
    string _s, s = "#";
    cin >> _s;
    for (char c : _s) s += c + "#"s;
    i32 n = (i32)s.size();
    DisjointSparseTable<Monoid> st((i32)s.size(), [&](i32 i) -> Monoid::T {
        return {(u64)s[i], (u64)s[i], 1};
    });
    for (i32 i = 1; i < n - 1; i++) {
        i32 l = 1, r = max({1, min(i + 1, n - i)}) + 1;
        binary_search(l, r, [&](i32 x) -> bool {
            auto cur = st.prod(i - x + 1, i + x);
            return cur[0] == cur[1];
        });
        cout << l - 1 << " \n"[i == n - 2];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}

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

#include <bits/stdc++.h>
using namespace std;

#line 2 "ds/disjoint_sparse_table.hpp"

template<class M> struct DisjointSparseTable {
    using T = typename M::T;
    DisjointSparseTable(const vector<T> &v) :
        DisjointSparseTable((int)v.size(), [&](int i) -> T { return v[i]; }) {}
    template<class G> DisjointSparseTable(int _n, G &&gen) : n(_n) {
        t.emplace_back(n);
        for (int i = 0; i < n; i++) t[0][i] = gen(i);
        for (int p = 1; 1 << p < n; p++) {
            t.emplace_back(n);
            for (int mid = 1 << p; mid < n; mid += 1 << (p + 1)) {
                t[p][mid - 1] = gen(mid - 1);
                for (int j = mid - 2; j >= mid - (1 << p); j--)
                    t[p][j] = M::op(gen(j), t[p][j + 1]);
                t[p][mid] = gen(mid);
                for (int j = mid + 1; j < min(mid + (1 << p), n); j++)
                    t[p][j] = M::op(t[p][j - 1], gen(j));
            }
        }
    }

    T prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= n);
        if (l == r) return M::id();
        r--;
        if (l == r) return t[0][l];
        int p = __builtin_clz(1) - __builtin_clz(l ^ r);
        return M::op(t[p][l], t[p][r]);
    }

  private:
    int n;
    vector<vector<T>> t;
};
#line 2 "ds/rolling_hash_static.hpp"

template<int id = 0> struct RollingHashStatic {
    using u64 = uint64_t;
    static u64 gen_base() noexcept {
        mt19937_64 rng((u64)make_unique<char>().get());
        uniform_int_distribution<u64> dist(1024, mod - 1);
        return dist(rng);
    }

    static inline u64 base = gen_base();

    static u64 concat(u64 l, u64 r, int lenr) noexcept {
        return add(mul(l, pow(lenr)), r);
    }

  private:
    static inline vector<u64> power{1};
    static u64 pow(int i) {
        while (power.size() <= i) power.push_back(mul(power.back(), base));
        return power[i];
    }

    static constexpr u64 mod = (1ull << 61) - 1;
    static constexpr u64 mask30 = (1u << 30) - 1;
    static constexpr u64 mask31 = (1u << 31) - 1;
    static constexpr u64 fast_mod(u64 x) noexcept {
        return add(x >> 61, x & mod);
    }
    static constexpr u64 add(u64 a, u64 b) noexcept {
        return (a += b) < mod ? a : a - mod;
    }
    static constexpr u64 mul(u64 a, u64 b) noexcept {
        u64 ha = a >> 31, la = a & mask31;
        u64 hb = b >> 31, lb = b & mask31;
        u64 m = ha * lb + la * hb;
        u64 hm = m >> 30, lm = m & mask30;
        return fast_mod(ha * hb * 2 + hm + (lm << 31) + la * lb);
    }
};
#line 2 "other/types.hpp"

using i8 = int8_t;
using u8 = uint8_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using f32 = float;
using f64 = double;
using f80 = long double;
using str = string;
template<class T> using vec = vector<T>;
template<class E = i32> using graph = vec<vec<E>>;
#line 9 "test/yosupo/string/enumerate_palindromes_rolling_hash.test.cpp"

struct Monoid {
    using hasher = RollingHashStatic<>;
    using T = array<u64, 3>;
    static T id() { return {}; }
    static T op(const T &l, const T &r) {
        return {
            hasher::concat(l[0], r[0], (i32)r[2]),
            hasher::concat(r[1], l[1], (i32)l[2]),
            l[2] + r[2],
        };
    }
};

template<class F, class I = i32> void binary_search(I &l, I &r, F &&pred) {
    while (r - l > 1) {
        I m = l + (r - l) / 2;
        (pred(m) ? l : r) = m;
    }
}

void solve() {
    string _s, s = "#";
    cin >> _s;
    for (char c : _s) s += c + "#"s;
    i32 n = (i32)s.size();
    DisjointSparseTable<Monoid> st((i32)s.size(), [&](i32 i) -> Monoid::T {
        return {(u64)s[i], (u64)s[i], 1};
    });
    for (i32 i = 1; i < n - 1; i++) {
        i32 l = 1, r = max({1, min(i + 1, n - i)}) + 1;
        binary_search(l, r, [&](i32 x) -> bool {
            auto cur = st.prod(i - x + 1, i + x);
            return cur[0] == cur[1];
        });
        cout << l - 1 << " \n"[i == n - 2];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	all_same_00	AC	668 ms	484 MB
g++	all_same_01	AC	665 ms	485 MB
g++	all_same_02	AC	665 ms	484 MB
g++	all_same_03	AC	677 ms	485 MB
g++	all_same_04	AC	677 ms	484 MB
g++	example_00	AC	5 ms	4 MB
g++	example_01	AC	4 ms	4 MB
g++	example_02	AC	4 ms	4 MB
g++	example_03	AC	4 ms	4 MB
g++	max_random_00	AC	792 ms	480 MB
g++	max_random_01	AC	791 ms	479 MB
g++	max_random_02	AC	792 ms	480 MB
g++	max_random_03	AC	823 ms	480 MB
g++	max_random_04	AC	796 ms	480 MB
g++	random_00	AC	602 ms	375 MB
g++	random_01	AC	730 ms	445 MB
g++	random_02	AC	78 ms	47 MB
g++	random_03	AC	689 ms	412 MB
g++	random_04	AC	426 ms	269 MB
g++	small_00	AC	6 ms	4 MB
g++	small_01	AC	5 ms	4 MB
g++	small_02	AC	5 ms	4 MB
g++	small_03	AC	6 ms	4 MB
g++	small_04	AC	5 ms	4 MB
clang++	all_same_00	AC	769 ms	484 MB
clang++	all_same_01	AC	781 ms	485 MB
clang++	all_same_02	AC	783 ms	485 MB
clang++	all_same_03	AC	773 ms	484 MB
clang++	all_same_04	AC	778 ms	485 MB
clang++	example_00	AC	5 ms	4 MB
clang++	example_01	AC	4 ms	4 MB
clang++	example_02	AC	4 ms	4 MB
clang++	example_03	AC	4 ms	4 MB
clang++	max_random_00	AC	929 ms	480 MB
clang++	max_random_01	AC	919 ms	480 MB
clang++	max_random_02	AC	922 ms	480 MB
clang++	max_random_03	AC	917 ms	480 MB
clang++	max_random_04	AC	918 ms	479 MB
clang++	random_00	AC	697 ms	376 MB
clang++	random_01	AC	854 ms	445 MB
clang++	random_02	AC	85 ms	47 MB
clang++	random_03	AC	777 ms	413 MB
clang++	random_04	AC	494 ms	270 MB
clang++	small_00	AC	6 ms	4 MB
clang++	small_01	AC	6 ms	4 MB
clang++	small_02	AC	5 ms	4 MB
clang++	small_03	AC	6 ms	4 MB
clang++	small_04	AC	5 ms	4 MB