test/helloworld/rolling-hash.test.cpp

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <bits/stdc++.h>

#include "../../String/rolling-hash.hpp"

#include "../../Util/randoms.hpp"
#include "../../Util/all-macro.hpp"
#include "../../Util/rep-macro.hpp"
#include "../../Util/Debug/errln.hpp"

using namespace std;
namespace rnd = arumakan::random;
using RH = RollingHash<17273747>;

const auto testdatas = []() -> vector<pair<string, RH>> {
    string s1 = "a";
    string s2 = "zzzzz";
    string s3 = rnd::randomValueContainer<string>('a', 'b', 30, 50);
    string s4 = rnd::randomValueContainer<string>('x', 'z', 30, 50);

    return {
        {s1, RH(all(s1))},
        {s2, RH(all(s2))},
        {s3, RH(all(s3))},
        {s4, RH(all(s4))},
    };
}();

void test_hash() {
    for (const auto& [str, rolhash] : testdatas) {
        assert(rolhash.hash() == rolhash.rangeHash(0, str.length()));
    }

    errln("OK");
}

void test_rangeHash_and_substr() {
    for (const auto& [str, rolhash] : testdatas) {
        const auto N = str.length();
        rep(l1, 0, N) rep(r1, l1 + 1, N) {
            rep(l2, 0, N) rep(r2, l2 + 1, N) {
                const auto len1 = r1 - l1;
                const auto len2 = r2 - l2;

                const bool equality_expected = string_view(str).substr(l1, len1) == string_view(str).substr(l2, len2);
                const bool equality_rangeHash = rolhash.rangeHash(l1, r1) == rolhash.rangeHash(l2, r2);
                const bool equality_substr = rolhash.substr(l1, len1) == rolhash.substr(l2, len2);
                assert(equality_rangeHash == equality_expected);
                assert(equality_substr == equality_expected);
            }
        }
    }

    errln("OK");
}

void test_concat() {
    vector<int> a{1, 2, 3, 1, 2, 3};
    RH rolhash(all(a));

    const auto N = a.size();
    rep(l, 0, N) rep(m, l + 1, N) rep(r, m + 1, N) {
        const auto leftHash = rolhash.rangeHash(l, m);
        const auto rightHash = rolhash.rangeHash(m, r);
        const auto got = rolhash.concat(leftHash, rightHash, r - m);
        const auto expected = rolhash.rangeHash(l, r);
        assert(got == expected);
    }
    errln("OK");
}

int main() {
    std::cout << "Hello World" << std::endl;

    test_hash();
    test_rangeHash_and_substr();
    test_concat();

    return 0;
}

#line 1 "test/helloworld/rolling-hash.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <bits/stdc++.h>

#line 2 "String/rolling-hash.hpp"

#line 7 "String/rolling-hash.hpp"

/**
 * @brief Rolling-Hash (ローリングハッシュ, mod値 $2^{61} - 1$ 固定)
 * @see https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
 */
template <uint_fast64_t Base>
class RollingHash {
public:
    using u64 = uint_fast64_t;
    using u128 = __uint128_t;
    static constexpr u64 MOD = (1uL << 61) - 1;
    static constexpr u64 BASE = Base;

private:
    std::vector<u64> m_hash;

public:
    RollingHash() = default;

    template <class InputIter>
    RollingHash(InputIter begin, InputIter end)
        : m_hash(std::distance(begin, end) + 1, 0) {
        if (powArray().empty()) {
            powArray().reserve(1e6);
            powArray().emplace_back(1);
        }
        growPowArray(m_hash.size());

        size_t i;
        InputIter itr;
        for (itr = begin, i = 0; itr != end; ++itr, ++i) {
            m_hash[i + 1] = add(mul(m_hash[i], BASE), *itr);
        }
    }

    //! 文字列全体のハッシュ値
    u64 hash() const { return m_hash.back(); }

    //! 半開区間 [l, r) のハッシュ値
    u64 rangeHash(size_t l, size_t r) const {
        assert(l < r && r < m_hash.size());
        return add(m_hash[r], MOD - mul(m_hash[l], powArray()[r - l]));
    }

    //! rangeHash(begin, begin + length) と等価
    u64 substr(size_t begin, size_t length) const { return rangeHash(begin, begin + length); }

    //! もとの文字列の長さ
    size_t size() const { return m_hash.size() - 1; }

    //! 連結した文字列 (leftStr + rightStr) のハッシュ値
    static u64 concat(u64 leftHash, u64 rightHash, size_t rightLength) {
        growPowArray(rightLength);
        return add(mul(leftHash, powArray()[rightLength]), rightHash);
    }

private:
    static inline std::vector<u64>& powArray() {
        static std::vector<u64> p;
        return p;
    }

    static constexpr inline u64 add(u64 a, u64 b) noexcept {
        if ((a += b) >= MOD) a -= MOD;
        return a;
    }

    static constexpr inline u64 mul(u128 a, u128 b) noexcept {
        const auto c = a * b;
        return add(static_cast<u64>(c >> 61), static_cast<u64>(c & MOD));
    }

    static inline void growPowArray(size_t len) {
        ++len;
        while (powArray().size() < len) {
            powArray().emplace_back(mul(powArray().back(), BASE));
        }
    }
};
#line 5 "test/helloworld/rolling-hash.test.cpp"

#line 2 "Util/randoms.hpp"

#line 5 "Util/randoms.hpp"

/**
 * @brief randoms (randint()とかchoice()とか)
 */
namespace arumakan::random {

std::mt19937 mt(std::random_device{}());

//! 閉区間[min, max] の乱数を一様分布で生成する
template <class Integer>
Integer randint(Integer min, Integer max) {
    return std::uniform_int_distribution<Integer>(min, max)(mt);
}

//! dest に randint(sizeMin, sizeMax) 回 randint(valueMin, valueMax) を格納する
template <class OutputIter, class Integer>
OutputIter randomValueContainer(OutputIter dest, Integer valueMin, Integer valueMax, size_t sizeMin, size_t sizeMax) {
    auto size = randint(sizeMin, sizeMax);
    while (size--) {
        *dest = randint(valueMin, valueMax);
        ++dest;
    }
    return dest;
}

//! 要素数が randint(sizeMin, sizeMax) の randint(valueMin, valueMax) を生成する
template <class Container, class Integer>
Container randomValueContainer(Integer valueMin, Integer valueMax, size_t sizeMin, size_t sizeMax) {
    Container ret;
    randomValueContainer(std::back_inserter(ret), valueMin, valueMax, sizeMin, sizeMax);
    return ret;
}

//! [begin, end) の範囲のうちひとつをランダムに選んで返す
template <class RandomAccessIter>
auto choice(RandomAccessIter begin, RandomAccessIter end) {
    const auto i = randint<size_t>(0, std::distance(begin, end));
    return begin[i];
}

}  // namespace rand
#line 2 "Util/all-macro.hpp"

/**
 * @brief all()マクロ
 */
#define all(x) std::begin(x), std::end(x)
#define rall(x) std::rbegin(x), std::rend(x)
#line 2 "Util/rep-macro.hpp"

/**
 * @brief rep()マクロ
 */
#define rep(i, begin, end) for (int64_t i = (begin), i##_end = (end); i < i##_end; ++i)
#define repc(i, begin, last) for (int64_t i = (begin), i##_last = (last); i <= i##_last; ++i)
#define repr(i, begin, last) for (int64_t i = (begin), i##_last = (last); i >= i##_last; --i)
#line 2 "Util/Debug/errln.hpp"

#line 4 "Util/Debug/errln.hpp"

/**
 * @brief errln() (println()のstderr版, デバッグ時のみ有効)
 */
inline void eprintln() {
    std::clog << std::endl;
}
template <class Head, class... Tail>
inline void eprintln(Head&& head, Tail&&... tail) {
    std::clog << head << &" "[!sizeof...(tail)];
    eprintln(std::forward<Tail>(tail)...);
}

#ifdef LOCAL_DEBUG
#define errln(...) std::clog << __FILE__ << "(" << __LINE__ << ")[" << __func__ << "()]: ", eprintln(__VA_ARGS__)
#else
#define errln(...) ((void)0)
#endif
#line 10 "test/helloworld/rolling-hash.test.cpp"

using namespace std;
namespace rnd = arumakan::random;
using RH = RollingHash<17273747>;

const auto testdatas = []() -> vector<pair<string, RH>> {
    string s1 = "a";
    string s2 = "zzzzz";
    string s3 = rnd::randomValueContainer<string>('a', 'b', 30, 50);
    string s4 = rnd::randomValueContainer<string>('x', 'z', 30, 50);

    return {
        {s1, RH(all(s1))},
        {s2, RH(all(s2))},
        {s3, RH(all(s3))},
        {s4, RH(all(s4))},
    };
}();

void test_hash() {
    for (const auto& [str, rolhash] : testdatas) {
        assert(rolhash.hash() == rolhash.rangeHash(0, str.length()));
    }

    errln("OK");
}

void test_rangeHash_and_substr() {
    for (const auto& [str, rolhash] : testdatas) {
        const auto N = str.length();
        rep(l1, 0, N) rep(r1, l1 + 1, N) {
            rep(l2, 0, N) rep(r2, l2 + 1, N) {
                const auto len1 = r1 - l1;
                const auto len2 = r2 - l2;

                const bool equality_expected = string_view(str).substr(l1, len1) == string_view(str).substr(l2, len2);
                const bool equality_rangeHash = rolhash.rangeHash(l1, r1) == rolhash.rangeHash(l2, r2);
                const bool equality_substr = rolhash.substr(l1, len1) == rolhash.substr(l2, len2);
                assert(equality_rangeHash == equality_expected);
                assert(equality_substr == equality_expected);
            }
        }
    }

    errln("OK");
}

void test_concat() {
    vector<int> a{1, 2, 3, 1, 2, 3};
    RH rolhash(all(a));

    const auto N = a.size();
    rep(l, 0, N) rep(m, l + 1, N) rep(r, m + 1, N) {
        const auto leftHash = rolhash.rangeHash(l, m);
        const auto rightHash = rolhash.rangeHash(m, r);
        const auto got = rolhash.concat(leftHash, rightHash, r - m);
        const auto expected = rolhash.rangeHash(l, r);
        assert(got == expected);
    }
    errln("OK");
}

int main() {
    std::cout << "Hello World" << std::endl;

    test_hash();
    test_rangeHash_and_substr();
    test_concat();

    return 0;
}