test/string/rolling_hash_2.test.cpp

View this file on GitHub
Last update: 2025-04-27 17:28:05+09:00
Problem: https://judge.yosupo.jp/problem/enumerate_palindromes

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_palindromes"
#include "../../string/Rolling_Hash.hpp"
#include <iostream>
#include <algorithm>

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::string S;
    std::cin >> S;
    int N = S.size();
    std::vector<int> T(N);
    for (int i = 0; i < N; i++) T[i] = S[i] - 'a';
    po167::RollingHash A(T);
    std::reverse(T.begin(), T.end());
    po167::RollingHash B(T);
    for (int i = 0; i < N * 2 - 1; i++){
        int l = N - (i + 1) / 2;
        int r = 1 + i / 2;
        int a = 0, b = N + 1 - std::max(l, r);
        while (b - a > 1){
            int m = (a + b) / 2;
            if (A.get(r, r + m) == B.get(l, l + m)) a = m;
            else b = m;
        }
        std::cout << a * 2 + ((i + 1) & 1) << (i + 1 == N * 2 - 1 ? "\n" : " ");
    }
}

#line 1 "test/string/rolling_hash_2.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_palindromes"
#line 2 "modint/mint61.hpp"

// https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
namespace po167{
struct mint61{
    using u64 = unsigned long long;
    static constexpr u64 MOD = (1ULL << 61) - 1;
    static constexpr u64 MASK30 = (1ULL << 30) - 1;
    static constexpr u64 MASK31 = (1ULL << 31) - 1;
    u64  x;
    u64 calcmod(u64 a){
        u64 au = (a >> 61);
        u64 ad = (a & MOD);
        u64 res = au + ad;
        if (res >= MOD) res -= MOD;
        return res;
    }
    mint61(){ x = 0;}
    mint61(long long x_){
        while (x_ < 0) x_ += MOD;
        x = calcmod(x_);
    }
    mint61 &operator+=(mint61 b){
        if ((x += b.x) >= MOD) x -= MOD;
        return *this;
    }
    mint61 &operator-=(mint61 b){
        if (x >= b.x) x -= b.x;
        else{
            x += MOD;
            x -= b.x;
        }
        return *this;
    }
    mint61 &operator*=(mint61 b){
        u64 au = (x >> 31);
        u64 ad = (x & MASK31);
        u64 bu = (b.x >> 31);
        u64 bd = (b.x & MASK31);
        u64 mid = ad * bu + au * bd;
        u64 midu = (mid >> 30);
        u64 midd = (mid & MASK30);
        x = calcmod(au * bu * 2 + midu + (midd << 31) + ad * bd);
        return *this;
    }
    friend mint61 operator+(mint61 a, mint61 b){return a += b;}
    friend mint61 operator-(mint61 a, mint61 b){return a -= b;}
    friend mint61 operator*(mint61 a, mint61 b){return a *= b;}
    friend bool operator==(mint61 a, mint61 b){return a.x == b.x;}
    friend bool operator!=(mint61 a, mint61 b){return a.x != b.x;}
    mint61 pow(long long e) const {
        mint61 r = 1,b =*this;
        if (e < 0) e = MOD - 1 + e % (MOD - 1);
        while (e){
            if (e & 1) r *= b;
            b *= b;
            e >>= 1;
        }
        return r;
    }
};
}
#line 3 "string/Rolling_Hash.hpp"
#include <random>
#include <string>
#include <vector>

namespace po167{
struct RollingHash {
    using u64 = uint64_t;
    static inline const mint61 base = std::mt19937_64{std::random_device{}()}();
    int n;
    std::vector<mint61> hash, pow;
    RollingHash(const std::string& s): n(s.size()), hash(n + 1), pow(n + 1, 1) {
        for (int i = 0; i < n; i++) {
            pow[i + 1] = pow[i] * base;
            hash[i + 1] = hash[i] * base + s[i];
        }
    }
    template<class T>
    RollingHash(const std::vector<T> &v): n(v.size()), hash(n + 1), pow(n + 1, 1) {
        for (int i = 0; i < n; i++){
            pow[i + 1] = pow[i] * base;
            hash[i + 1] = hash[i] * base + v[i];
        }
    }
    mint61 get(int l, int r) const {
        return hash[r] - hash[l] * pow[r - l];
    }
};
}
#line 3 "test/string/rolling_hash_2.test.cpp"
#include <iostream>
#include <algorithm>

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::string S;
    std::cin >> S;
    int N = S.size();
    std::vector<int> T(N);
    for (int i = 0; i < N; i++) T[i] = S[i] - 'a';
    po167::RollingHash A(T);
    std::reverse(T.begin(), T.end());
    po167::RollingHash B(T);
    for (int i = 0; i < N * 2 - 1; i++){
        int l = N - (i + 1) / 2;
        int r = 1 + i / 2;
        int a = 0, b = N + 1 - std::max(l, r);
        while (b - a > 1){
            int m = (a + b) / 2;
            if (A.get(r, r + m) == B.get(l, l + m)) a = m;
            else b = m;
        }
        std::cout << a * 2 + ((i + 1) & 1) << (i + 1 == N * 2 - 1 ? "\n" : " ");
    }
}