test/unit/string_hash.test.cpp

• View this file on GitHub
• Last update: 2026-10-26 01:30:50+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A

Depends on

• Algebra: Concept (algebra/concept.hpp)
• Lazy Segment Tree (acted monoid wrapper) (datastructure/lazy_segtree.hpp)
• modint2305843009213693951 (math/modint2305843009213693951.hpp)
• Range Update Range Hash (string/range_update_range_hash.hpp)
• Rolling Hash (string/rolling_hash.hpp)
• String Hash (string/string_hash.hpp)

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <set>
#include <string>
#include <vector>

#include "string/range_update_range_hash.hpp"
#include "string/rolling_hash.hpp"
#include "string/string_hash.hpp"
int brute_cmp(const std::string& a, const std::string& b) {
    return a < b ? -1 : a == b ? 0 : 1;
}
int brute_lcp(const std::string& a, const std::string& b) {
    int i = 0;
    while (i < int(a.size()) && i < int(b.size()) && a[i] == b[i]) i++;
    return i;
}
int main() {
    std::mt19937 rng(7959);
    for (int trial = 0; trial < 200; trial++) {
        int n = 1 + rng() % 12, m = 1 + rng() % 12;
        int sigma = 1 + rng() % 3;
        std::string s(n, 'a'), t(m, 'a');
        for (auto& c : s) c = 'a' + rng() % sigma;
        for (auto& c : t) c = 'a' + rng() % sigma;
        rolling_hash<> rs(s);
        range_update_range_hash<> rt(t);
        assert(rs.size() == n && rt.size() == m);
        for (int q = 0; q < 30; q++) {
            if (rng() % 3 == 0) {
                int l = rng() % (m + 1), r = rng() % (m + 1);
                if (l > r) std::swap(l, r);
                char c = 'a' + rng() % sigma;
                rt.apply(l, r, c);
                for (int i = l; i < r; i++) t[i] = c;
            } else if (rng() % 3 == 0) {
                int p = rng() % m;
                char c = 'a' + rng() % sigma;
                rt.set(p, c);
                t[p] = c;
            }
            int l1 = rng() % (n + 1), r1 = rng() % (n + 1);
            if (l1 > r1) std::swap(l1, r1);
            int l2 = rng() % (m + 1), r2 = rng() % (m + 1);
            if (l2 > r2) std::swap(l2, r2);
            std::string a = s.substr(l1, r1 - l1), b = t.substr(l2, r2 - l2);
            assert((rs.prod(l1, r1) == rt.prod(l2, r2)) == (a == b));
            assert(lcp(rs, l1, r1, rt, l2, r2) == brute_lcp(a, b));
            assert(cmp(rs, l1, r1, rt, l2, r2) == brute_cmp(a, b));
            assert(cmp(rt, l2, r2, rs, l1, r1) == brute_cmp(b, a));
            int l3 = rng() % (n + 1), r3 = rng() % (n + 1);
            if (l3 > r3) std::swap(l3, r3);
            std::string c = s.substr(l3, r3 - l3);
            assert(cmp(rs, l1, r1, rs, l3, r3) == brute_cmp(a, c));
            assert(lcp(rs, l1, r1, rs, l3, r3) == brute_lcp(a, c));
            assert(rs.prod(l1, r1) + rs.prod(l3, r3) == rolling_hash<>(a + c).all_prod());
            assert(rs.prod(l1, r1) + rt.prod(l2, r2) == rolling_hash<>(a + b).all_prod());
            if (l1 < r1) assert(rs.get(l1) == string_hash<>(s[l1]));
            assert(rt.all_prod() == rolling_hash<>(t).all_prod());
            assert(rt.prod(l2, r2) == rolling_hash<>(b).all_prod());
        }
        {
            std::string r(n, 'a');
            char c = 'a' + rng() % sigma;
            for (auto& x : r) x = c;
            assert(string_hash<>::repeat(c, n) == rolling_hash<>(r).all_prod());
        }
        {
            std::set<string_hash<>> hs;
            std::set<std::string> ss;
            for (int l = 0; l <= n; l++)
                for (int r = l; r <= n; r++) hs.insert(rs.prod(l, r)), ss.insert(s.substr(l, r - l));
            assert(hs.size() == ss.size());
        }
    }
    {
        rolling_hash<2> rh(std::vector<int>{1, 2, 3});
        assert(rh.prod(0, 2) + rh.prod(2, 3) == rh.all_prod());
        assert(rh.prod(0, 0) == string_hash<2>());
        assert(rolling_hash<2>(std::string("")).all_prod() == string_hash<2>());
    }
    std::cout << "Hello World" << std::endl;
    return 0;
}

#line 1 "test/unit/string_hash.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <set>
#include <string>
#include <vector>

#line 4 "string/range_update_range_hash.hpp"

#line 2 "datastructure/lazy_segtree.hpp"
#include <atcoder/lazysegtree>

#line 2 "algebra/concept.hpp"
#include <concepts>
template <class M>
concept semigroup = requires(typename M::S a, typename M::S b) {
    { M::op(a, b) } -> std::same_as<typename M::S>;
};
template <class M>
concept monoid = semigroup<M> && requires {
    { M::e() } -> std::same_as<typename M::S>;
};
template <class G>
concept group = monoid<G> && requires(typename G::S a) {
    { G::inv(a) } -> std::same_as<typename G::S>;
};
template <class A>
concept action = requires(typename A::F f, typename A::F g) {
    { A::composition(f, g) } -> std::same_as<typename A::F>;
    { A::id() } -> std::same_as<typename A::F>;
    { A::composition_commutative } -> std::convertible_to<bool>;
};
template <class A>
concept acted_monoid = monoid<A> && action<A> && requires(typename A::S x, typename A::F f) {
    { A::mapping(f, x) } -> std::same_as<typename A::S>;
};
template <class R>
concept semiring = requires(typename R::S a, typename R::S b) {
    { R::add(a, b) } -> std::same_as<typename R::S>;
    { R::zero() } -> std::same_as<typename R::S>;
    { R::mul(a, b) } -> std::same_as<typename R::S>;
    { R::one() } -> std::same_as<typename R::S>;
};
#line 5 "datastructure/lazy_segtree.hpp"
template <acted_monoid A>
using lazy_segtree = atcoder::lazy_segtree<typename A::S, A::op, A::e, typename A::F, A::mapping, A::composition, A::id>;
#line 3 "string/string_hash.hpp"
#include <array>
#line 5 "string/string_hash.hpp"
#include <cstdint>
#include <numeric>
#line 9 "string/string_hash.hpp"

#line 5 "math/modint2305843009213693951.hpp"
struct modint2305843009213693951 {
    using mint = modint2305843009213693951;
    static constexpr uint64_t mod() {
        return m;
    }
    static mint raw(uint64_t v) {
        mint x;
        x._v = v;
        return x;
    }
    modint2305843009213693951() : _v(0) {}
    template <std::unsigned_integral T>
    modint2305843009213693951(T v) : _v(reduce(v)) {}
    template <std::signed_integral T>
    modint2305843009213693951(T v) {
        if (v >= 0) {
            _v = reduce(uint64_t(v));
        } else {
            uint64_t x = reduce(uint64_t(0) - uint64_t(v));
            _v = x == 0 ? 0 : m - x;
        }
    }
    uint64_t val() const {
        return _v;
    }
    mint& operator++() {
        if (++_v == m) _v = 0;
        return *this;
    }
    mint& operator--() {
        if (_v == 0) _v = m;
        _v--;
        return *this;
    }
    mint operator++(int) {
        mint r = *this;
        ++*this;
        return r;
    }
    mint operator--(int) {
        mint r = *this;
        --*this;
        return r;
    }
    mint& operator+=(const mint& rhs) {
        _v += rhs._v;
        if (_v >= m) _v -= m;
        return *this;
    }
    mint& operator-=(const mint& rhs) {
        _v += m - rhs._v;
        if (_v >= m) _v -= m;
        return *this;
    }
    mint& operator*=(const mint& rhs) {
        constexpr uint64_t mask31 = (uint64_t(1) << 31) - 1;
        constexpr uint64_t mask30 = (uint64_t(1) << 30) - 1;
        uint64_t au = _v >> 31, ad = _v & mask31;
        uint64_t bu = rhs._v >> 31, bd = rhs._v & mask31;
        uint64_t mid = ad * bu + au * bd;
        uint64_t mu = mid >> 30, md = mid & mask30;
        _v = reduce((au * bu << 1) + mu + (md << 31) + ad * bd);
        return *this;
    }
    mint& operator/=(const mint& rhs) {
        return *this *= rhs.inv();
    }
    mint operator+() const {
        return *this;
    }
    mint operator-() const {
        return mint() - *this;
    }
    mint pow(long long n) const {
        assert(0 <= n);
        mint x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    mint inv() const {
        assert(_v != 0);
        return pow(m - 2);
    }
    friend mint operator+(const mint& lhs, const mint& rhs) {
        return mint(lhs) += rhs;
    }
    friend mint operator-(const mint& lhs, const mint& rhs) {
        return mint(lhs) -= rhs;
    }
    friend mint operator*(const mint& lhs, const mint& rhs) {
        return mint(lhs) *= rhs;
    }
    friend mint operator/(const mint& lhs, const mint& rhs) {
        return mint(lhs) /= rhs;
    }
    friend bool operator==(const mint& lhs, const mint& rhs) {
        return lhs._v == rhs._v;
    }
    friend bool operator!=(const mint& lhs, const mint& rhs) {
        return lhs._v != rhs._v;
    }

private:
    static constexpr uint64_t m = (uint64_t(1) << 61) - 1;
    static constexpr uint64_t reduce(uint64_t v) {
        uint64_t x = (v >> 61) + (v & m);
        if (x >= m) x -= m;
        return x;
    }
    uint64_t _v;
};
#line 11 "string/string_hash.hpp"
template <int k = 1, class mint = modint2305843009213693951>
struct string_hash {
    static_assert(k >= 1);
    std::array<mint, k> val;
    int len;
    string_hash() : val{}, len(0) {}
    explicit string_hash(int c) : len(1) {
        val.fill(mint(c));
    }
    static string_hash repeat(int c, int n) {
        assert(0 <= n);
        string_hash h;
        h.len = n;
        for (int i = 0; i < k; i++) h.val[i] = mint(c) * pow_sum(i, n);
        return h;
    }
    friend string_hash operator+(const string_hash& a, const string_hash& b) {
        string_hash r;
        r.len = a.len + b.len;
        for (int i = 0; i < k; i++) r.val[i] = a.val[i] * pow(i, b.len) + b.val[i];
        return r;
    }
    string_hash& operator+=(const string_hash& b) {
        return *this = *this + b;
    }
    friend bool operator==(const string_hash& a, const string_hash& b) {
        return a.len == b.len && a.val == b.val;
    }
    friend bool operator<(const string_hash& a, const string_hash& b) {
        if (a.len != b.len) return a.len < b.len;
        for (int i = 0; i < k; i++) {
            if (a.val[i] != b.val[i]) return a.val[i].val() < b.val[i].val();
        }
        return false;
    }
    static mint base(int i) {
        return bases()[i];
    }
    static mint pow(int i, int n) {
        ensure(n);
        return pows()[i][n];
    }
    static mint pow_sum(int i, int n) {
        ensure(n);
        return pow_sums()[i][n];
    }

private:
    static std::array<mint, k> gen_bases() {
        std::mt19937_64 rng(std::random_device{}());
        std::array<mint, k> b;
        for (int i = 0; i < k; i++) {
            while (true) {
                uint64_t e = std::uniform_int_distribution<uint64_t>(1, mint::mod() - 1)(rng);
                if (std::gcd(e, uint64_t(mint::mod() - 1)) != 1) continue;
                b[i] = mint(37).pow(e);
                break;
            }
        }
        return b;
    }
    static std::array<mint, k>& bases() {
        static std::array<mint, k> b = gen_bases();
        return b;
    }
    static std::array<std::vector<mint>, k>& pows() {
        static std::array<std::vector<mint>, k> p = [] {
            std::array<std::vector<mint>, k> p;
            for (auto& v : p) v.assign(1, mint(1));
            return p;
        }();
        return p;
    }
    static std::array<std::vector<mint>, k>& pow_sums() {
        static std::array<std::vector<mint>, k> s = [] {
            std::array<std::vector<mint>, k> s;
            for (auto& v : s) v.assign(1, mint(0));
            return s;
        }();
        return s;
    }
    static void ensure(int n) {
        auto& p = pows();
        auto& s = pow_sums();
        int sz = int(p[0].size());
        if (n < sz) return;
        int m = std::max(n + 1, 2 * sz);
        for (int i = 0; i < k; i++) {
            p[i].resize(m);
            s[i].resize(m);
            for (int j = sz; j < m; j++) {
                p[i][j] = p[i][j - 1] * base(i);
                s[i][j] = s[i][j - 1] + p[i][j - 1];
            }
        }
    }
};
template <class A, class B>
int lcp(A& a, int l1, int r1, B& b, int l2, int r2) {
    int ok = 0, ng = std::min(r1 - l1, r2 - l2) + 1;
    while (ng - ok > 1) {
        int mid = (ok + ng) / 2;
        (a.prod(l1, l1 + mid) == b.prod(l2, l2 + mid) ? ok : ng) = mid;
    }
    return ok;
}
template <class A, class B>
int cmp(A& a, int l1, int r1, B& b, int l2, int r2) {
    int x = lcp(a, l1, r1, b, l2, r2);
    bool ea = l1 + x == r1, eb = l2 + x == r2;
    if (ea && eb) return 0;
    if (ea) return -1;
    if (eb) return 1;
    return a.get(l1 + x).val[0].val() < b.get(l2 + x).val[0].val() ? -1 : 1;
}
#line 7 "string/range_update_range_hash.hpp"
template <int k = 1, class mint = modint2305843009213693951>
struct range_update_range_hash {
    using H = string_hash<k, mint>;
    range_update_range_hash() : n(0) {}
    template <class Iterable>
    explicit range_update_range_hash(const Iterable& s) {
        std::vector<H> v;
        for (auto&& c : s) v.emplace_back(int(c));
        n = int(v.size());
        seg = lazy_segtree<A>(v);
    }
    int size() const {
        return n;
    }
    void set(int p, int c) {
        assert(0 <= c);
        seg.set(p, H(c));
    }
    void apply(int l, int r, int c) {
        assert(0 <= c);
        seg.apply(l, r, c);
    }
    H prod(int l, int r) {
        return seg.prod(l, r);
    }
    H get(int p) {
        return seg.get(p);
    }
    H all_prod() {
        return seg.all_prod();
    }

private:
    struct A {
        using S = H;
        using F = int;
        static S op(S a, S b) {
            return a + b;
        }
        static S e() {
            return S();
        }
        static S mapping(F f, S x) {
            return f < 0 ? x : H::repeat(f, x.len);
        }
        static F composition(F f, F g) {
            return f < 0 ? g : f;
        }
        static F id() {
            return -1;
        }
        static constexpr bool composition_commutative = false;
    };
    int n;
    lazy_segtree<A> seg;
};
#line 5 "string/rolling_hash.hpp"

#line 7 "string/rolling_hash.hpp"
template <int k = 1, class mint = modint2305843009213693951>
struct rolling_hash {
    using H = string_hash<k, mint>;
    rolling_hash() : n(0) {}
    template <class Iterable>
    explicit rolling_hash(const Iterable& s) {
        std::vector<int> a;
        for (auto&& c : s) a.push_back(int(c));
        n = int(a.size());
        for (int i = 0; i < k; i++) {
            h[i].assign(n + 1, mint(0));
            for (int j = 0; j < n; j++) h[i][j + 1] = h[i][j] * H::base(i) + mint(a[j]);
        }
    }
    int size() const {
        return n;
    }
    H prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= n);
        H res;
        res.len = r - l;
        for (int i = 0; i < k; i++) res.val[i] = h[i][r] - h[i][l] * H::pow(i, r - l);
        return res;
    }
    H get(int p) const {
        return prod(p, p + 1);
    }
    H all_prod() const {
        return prod(0, n);
    }

private:
    int n;
    std::array<std::vector<mint>, k> h;
};
#line 13 "test/unit/string_hash.test.cpp"
int brute_cmp(const std::string& a, const std::string& b) {
    return a < b ? -1 : a == b ? 0 : 1;
}
int brute_lcp(const std::string& a, const std::string& b) {
    int i = 0;
    while (i < int(a.size()) && i < int(b.size()) && a[i] == b[i]) i++;
    return i;
}
int main() {
    std::mt19937 rng(7959);
    for (int trial = 0; trial < 200; trial++) {
        int n = 1 + rng() % 12, m = 1 + rng() % 12;
        int sigma = 1 + rng() % 3;
        std::string s(n, 'a'), t(m, 'a');
        for (auto& c : s) c = 'a' + rng() % sigma;
        for (auto& c : t) c = 'a' + rng() % sigma;
        rolling_hash<> rs(s);
        range_update_range_hash<> rt(t);
        assert(rs.size() == n && rt.size() == m);
        for (int q = 0; q < 30; q++) {
            if (rng() % 3 == 0) {
                int l = rng() % (m + 1), r = rng() % (m + 1);
                if (l > r) std::swap(l, r);
                char c = 'a' + rng() % sigma;
                rt.apply(l, r, c);
                for (int i = l; i < r; i++) t[i] = c;
            } else if (rng() % 3 == 0) {
                int p = rng() % m;
                char c = 'a' + rng() % sigma;
                rt.set(p, c);
                t[p] = c;
            }
            int l1 = rng() % (n + 1), r1 = rng() % (n + 1);
            if (l1 > r1) std::swap(l1, r1);
            int l2 = rng() % (m + 1), r2 = rng() % (m + 1);
            if (l2 > r2) std::swap(l2, r2);
            std::string a = s.substr(l1, r1 - l1), b = t.substr(l2, r2 - l2);
            assert((rs.prod(l1, r1) == rt.prod(l2, r2)) == (a == b));
            assert(lcp(rs, l1, r1, rt, l2, r2) == brute_lcp(a, b));
            assert(cmp(rs, l1, r1, rt, l2, r2) == brute_cmp(a, b));
            assert(cmp(rt, l2, r2, rs, l1, r1) == brute_cmp(b, a));
            int l3 = rng() % (n + 1), r3 = rng() % (n + 1);
            if (l3 > r3) std::swap(l3, r3);
            std::string c = s.substr(l3, r3 - l3);
            assert(cmp(rs, l1, r1, rs, l3, r3) == brute_cmp(a, c));
            assert(lcp(rs, l1, r1, rs, l3, r3) == brute_lcp(a, c));
            assert(rs.prod(l1, r1) + rs.prod(l3, r3) == rolling_hash<>(a + c).all_prod());
            assert(rs.prod(l1, r1) + rt.prod(l2, r2) == rolling_hash<>(a + b).all_prod());
            if (l1 < r1) assert(rs.get(l1) == string_hash<>(s[l1]));
            assert(rt.all_prod() == rolling_hash<>(t).all_prod());
            assert(rt.prod(l2, r2) == rolling_hash<>(b).all_prod());
        }
        {
            std::string r(n, 'a');
            char c = 'a' + rng() % sigma;
            for (auto& x : r) x = c;
            assert(string_hash<>::repeat(c, n) == rolling_hash<>(r).all_prod());
        }
        {
            std::set<string_hash<>> hs;
            std::set<std::string> ss;
            for (int l = 0; l <= n; l++)
                for (int r = l; r <= n; r++) hs.insert(rs.prod(l, r)), ss.insert(s.substr(l, r - l));
            assert(hs.size() == ss.size());
        }
    }
    {
        rolling_hash<2> rh(std::vector<int>{1, 2, 3});
        assert(rh.prod(0, 2) + rh.prod(2, 3) == rh.all_prod());
        assert(rh.prod(0, 0) == string_hash<2>());
        assert(rolling_hash<2>(std::string("")).all_prod() == string_hash<2>());
    }
    std::cout << "Hello World" << std::endl;
    return 0;
}

Back to top page