cp-library-cpp

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub suisen-cp/cp-library-cpp

:heavy_check_mark: test/src/string/compare_substring/dummy.test.cpp

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"

#include <iostream>
#include <random>

#include "library/string/compare_substring.hpp"

template <typename T>
std::ostream& operator<<(std::ostream& out, const std::vector<T>& v) {
    const std::size_t n = v.size();
    for (std::size_t i = 0; i < n; ++i) {
        out << v[i];
        if (i + 1 != n) out << ' ';
    }
    return out;
}

template <typename Container>
auto subsegment(const Container& container, int l, int r) {
    Container res;
    std::copy(std::next(std::begin(container), l), std::next(std::begin(container), r), std::back_inserter(res));
    return res;
}

template <typename Container>
void test(const Container& s) {
    std::cerr << "  [\033[32mINFO\033[m] Test \"" << s << "\" ... ";

    auto naive_compare = [&s](int l1, int r1, int l2, int r2) {
        auto s1 = subsegment(s, l1, r1);
        auto s2 = subsegment(s, l2, r2);
        return s1 < s2 ? -1 : s1 > s2 ? 1 : 0;
    };
    suisen::CompareSubstring<suisen::compare_substring_rmq::SparseTableRmQ> fast_compare(s);

    const int n = std::size(s);
    for (int l1 = 0; l1 <= n; ++l1) for (int r1 = l1; r1 <= n; ++r1) {
        for (int l2 = 0; l2 <= n; ++l2) for (int r2 = l2; r2 <= n; ++r2) {
            int res1 = naive_compare(l1, r1, l2, r2);
            int res2 = fast_compare(l1, r1, l2, r2);

            if (res1 != res2) {
                auto to_symbol = [](int res) { return res == 0 ? '=' : res > 0 ? '>' : '<'; };

                std::cerr << "\033[31mFailed.\033[m" << std::endl;
                std::cerr << "  compare s[" << l1 << "," << r1 << ") s[" << l2 << "," << r2 << "):" << std::endl;
                std::cerr << "    s[" << l1 << "," << r1 << ") = \"" << subsegment(s, l1, r1) << "\"" << std::endl;
                std::cerr << "    s[" << l2 << "," << r2 << ") = \"" << subsegment(s, l2, r2) << "\"" << std::endl;
                std::cerr << "    expected : " << to_symbol(res1) << std::endl;
                std::cerr << "    actual   : " << to_symbol(res2) << std::endl;

                std::cerr << "[\033[31mERROR\033[m] Test Failed." << std::endl;

                assert(false);
            }
        }
    }
    std::cerr << "\033[32mOK.\033[m" << std::endl;
}

std::string random_lowercase_alphabet(int len, int alphabet_size, uint32_t seed = 0) {
    std::mt19937 rng{ seed ? seed : std::random_device{}() };
    std::uniform_int_distribution<int> dist(0, alphabet_size - 1);
    std::string res(len, '?');
    std::generate(std::begin(res), std::end(res), [&] { return 'a' + dist(rng); });
    return res;
}

std::vector<uint32_t> random_vector_of_uint32_t(int len, uint32_t max_value = std::numeric_limits<uint32_t>::max(), uint32_t seed = 0) {
    std::mt19937 rng{ seed ? seed : std::random_device{}() };
    std::uniform_int_distribution<uint32_t> dist(0, max_value);
    std::vector<uint32_t> res(len);
    std::generate(std::begin(res), std::end(res), [&] { return dist(rng); });
    return res;
}

void run_tests() {
    std::cerr << "[\033[32mINFO\033[m] Handmade string..." << std::endl;
    test(std::string("abracadabra"));
    std::cerr << "[\033[32mINFO\033[m] OK." << std::endl;

    std::cerr << "[\033[32mINFO\033[m] Random string of lowercase alphabets..." << std::endl;
    test(random_lowercase_alphabet(10, 1));
    test(random_lowercase_alphabet(30, 2));
    test(random_lowercase_alphabet(30, 26));
    std::cerr << "[\033[32mINFO\033[m] OK." << std::endl;

    std::cerr << "[\033[32mINFO\033[m] Random vector of integers..." << std::endl;
    test(random_vector_of_uint32_t(10, 0));
    test(random_vector_of_uint32_t(30, 1));
    test(random_vector_of_uint32_t(30, 25));
    test(random_vector_of_uint32_t(30));
    std::cerr << "[\033[32mINFO\033[m] OK." << std::endl;
}

int main() {
    run_tests();

    std::cout << "Hello World" << std::endl;
    return 0;
}
#line 1 "test/src/string/compare_substring/dummy.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"

#include <iostream>
#include <random>

#line 1 "library/string/compare_substring.hpp"



#include <atcoder/segtree>
#include <atcoder/string>

#line 1 "library/datastructure/sparse_table.hpp"



#include <vector>

namespace suisen {
    template <typename T, T(*op)(T, T), T(*e)()>
    struct SparseTable {
        SparseTable() = default;
        SparseTable(std::vector<T>&& a) : n(a.size()), log(floor_log2(n)), table(log + 1), flog(n + 1, 0) {
            build_table(std::move(a));
            build_flog_table();
        }
        SparseTable(const std::vector<T>& a) : SparseTable(std::vector<T>(a)) {}
        T operator()(int l, int r) const {
            if (l >= r) return e();
            int i = flog[r - l];
            return op(table[i][l], table[i][r - (1 << i)]);
        }
        T prod(int l, int r) const {
            return (*this)(l, r);
        }
    private:
        int n;
        int log;
        std::vector<std::vector<T>> table;
        std::vector<int> flog;

        void build_table(std::vector<T>&& a) {
            table[0] = std::move(a);
            for (int i = 0; i < log; ++i) {
                int lmax = n - (1 << (i + 1));
                table[i + 1].resize(lmax + 1);
                for (int l = 0; l <= lmax; ++l) table[i + 1][l] = op(table[i][l], table[i][l + (1 << i)]);
            }
        }
        void build_flog_table() {
            for (int l = 0; l < log; ++l) {
                std::fill(flog.begin() + (1 << l), flog.begin() + (1 << (l + 1)), l);
            }
            std::fill(flog.begin() + (1 << log), flog.end(), log);
        }
        static int floor_log2(int i) {
            return 31 - __builtin_clz(i);
        }
    };
} // namespace suisen


#line 8 "library/string/compare_substring.hpp"

namespace suisen {
    namespace internal::compare_substring {
        constexpr int op(int x, int y) { return std::min(x, y); }
        constexpr int e() { return std::numeric_limits<int>::max(); }
    }
    namespace compare_substring_rmq {
        using SegmentTreeRmQ = atcoder::segtree<int, internal::compare_substring::op, internal::compare_substring::e>;
        using SparseTableRmQ = SparseTable<int, internal::compare_substring::op, internal::compare_substring::e>;
    }
    template <typename RmQ = compare_substring_rmq::SparseTableRmQ>
    struct CompareSubstring {
        CompareSubstring() = default;
        CompareSubstring(const std::vector<int> &sa, const std::vector<int> &lcp) : _n(sa.size()), _sa_inv(_n), _lcp_min(lcp) {
            for (int i = 0; i < _n; ++i) _sa_inv[sa[i]] = i;
        }
        template <typename T>
        CompareSubstring(const std::vector<T> &s) : CompareSubstring(s, atcoder::suffix_array(s), DUMMY_PARAMETER) {}
        template <typename T>
        CompareSubstring(const std::vector<T> &s, const T& upper) : CompareSubstring(s, atcoder::suffix_array(s, upper), DUMMY_PARAMETER) {}
        CompareSubstring(const std::string &s) : CompareSubstring(s, atcoder::suffix_array(s), DUMMY_PARAMETER) {}

        int lcp(int l1, int r1, int l2, int r2) const {
            assert(0 <= l1 and l1 <= r1 and r1 <= _n);
            assert(0 <= l2 and l2 <= r2 and r2 <= _n);
            if (l1 == r1 or l2 == r2) return 0;
            auto [i1, i2] = std::minmax(_sa_inv[l1], _sa_inv[l2]);
            return std::min(std::min(r1 - l1, r2 - l2), _lcp_min(i1, i2));
        }
        int compare(int l1, int r1, int l2, int r2) const {
            const int len = lcp(l1, r1, l2, r2);
            const int w1 = r1 - l1, w2 = r2 - l2;
            return len == w1 and len == w2 ? 0 : len == w1 ? -1 : len == w2 ? 1 : _sa_inv[l1 + len] < _sa_inv[l2 + len] ? -1 : 1;
        }
        int operator()(int l1, int r1, int l2, int r2) const {
            return compare(l1, r1, l2, r2);
        }

        int lcp(const std::pair<int, int> &seg1, const std::pair<int, int> &seg2) const {
            return lcp(seg1.first, seg1.second, seg2.first, seg2.second);
        }
        int compare(const std::pair<int, int> &seg1, const std::pair<int, int> &seg2) const {
            return compare(seg1.first, seg1.second, seg2.first, seg2.second);
        }
        int operator()(const std::pair<int, int> &seg1, const std::pair<int, int> &seg2) const {
            return compare(seg1, seg2);
        }

        struct Substring {
            int l, r;
            Substring() = default;
            Substring(int l, int r, CompareSubstring<RmQ> const * ptr) : l(l), r(r), _ptr(ptr) {}

            int size() const { return r - l; }

            int lcp(const Substring &rhs) const {
                return _ptr->lcp(l, r, rhs.l, rhs.r);
            }
            int compare(const Substring &rhs) const {
                assert(rhs._ptr == _ptr);
                return _ptr->compare(l, r, rhs.l, rhs.r);
            }
            bool operator==(const Substring &rhs) const { return compare(rhs) == 0; }
            bool operator!=(const Substring &rhs) const { return compare(rhs) != 0; }
            bool operator< (const Substring &rhs) const { return compare(rhs) <  0; }
            bool operator<=(const Substring &rhs) const { return compare(rhs) <= 0; }
            bool operator> (const Substring &rhs) const { return compare(rhs) >  0; }
            bool operator>=(const Substring &rhs) const { return compare(rhs) >= 0; }
        private:
            CompareSubstring<RmQ> const * _ptr;
        };

        Substring substr(int l, int r) const { return Substring(l, r, this); }
        Substring substr(const std::pair<int, int> &seg) const { return substr(seg.first, seg.second); }
    private:
        static constexpr bool DUMMY_PARAMETER{};
        int _n;
        std::vector<int> _sa_inv;
        RmQ _lcp_min;

        template <typename Container>
        CompareSubstring(const Container &s, const std::vector<int> &sa, bool) : CompareSubstring(sa, atcoder::lcp_array(s, sa)) {}
    };
} // namespace suisen


#line 7 "test/src/string/compare_substring/dummy.test.cpp"

template <typename T>
std::ostream& operator<<(std::ostream& out, const std::vector<T>& v) {
    const std::size_t n = v.size();
    for (std::size_t i = 0; i < n; ++i) {
        out << v[i];
        if (i + 1 != n) out << ' ';
    }
    return out;
}

template <typename Container>
auto subsegment(const Container& container, int l, int r) {
    Container res;
    std::copy(std::next(std::begin(container), l), std::next(std::begin(container), r), std::back_inserter(res));
    return res;
}

template <typename Container>
void test(const Container& s) {
    std::cerr << "  [\033[32mINFO\033[m] Test \"" << s << "\" ... ";

    auto naive_compare = [&s](int l1, int r1, int l2, int r2) {
        auto s1 = subsegment(s, l1, r1);
        auto s2 = subsegment(s, l2, r2);
        return s1 < s2 ? -1 : s1 > s2 ? 1 : 0;
    };
    suisen::CompareSubstring<suisen::compare_substring_rmq::SparseTableRmQ> fast_compare(s);

    const int n = std::size(s);
    for (int l1 = 0; l1 <= n; ++l1) for (int r1 = l1; r1 <= n; ++r1) {
        for (int l2 = 0; l2 <= n; ++l2) for (int r2 = l2; r2 <= n; ++r2) {
            int res1 = naive_compare(l1, r1, l2, r2);
            int res2 = fast_compare(l1, r1, l2, r2);

            if (res1 != res2) {
                auto to_symbol = [](int res) { return res == 0 ? '=' : res > 0 ? '>' : '<'; };

                std::cerr << "\033[31mFailed.\033[m" << std::endl;
                std::cerr << "  compare s[" << l1 << "," << r1 << ") s[" << l2 << "," << r2 << "):" << std::endl;
                std::cerr << "    s[" << l1 << "," << r1 << ") = \"" << subsegment(s, l1, r1) << "\"" << std::endl;
                std::cerr << "    s[" << l2 << "," << r2 << ") = \"" << subsegment(s, l2, r2) << "\"" << std::endl;
                std::cerr << "    expected : " << to_symbol(res1) << std::endl;
                std::cerr << "    actual   : " << to_symbol(res2) << std::endl;

                std::cerr << "[\033[31mERROR\033[m] Test Failed." << std::endl;

                assert(false);
            }
        }
    }
    std::cerr << "\033[32mOK.\033[m" << std::endl;
}

std::string random_lowercase_alphabet(int len, int alphabet_size, uint32_t seed = 0) {
    std::mt19937 rng{ seed ? seed : std::random_device{}() };
    std::uniform_int_distribution<int> dist(0, alphabet_size - 1);
    std::string res(len, '?');
    std::generate(std::begin(res), std::end(res), [&] { return 'a' + dist(rng); });
    return res;
}

std::vector<uint32_t> random_vector_of_uint32_t(int len, uint32_t max_value = std::numeric_limits<uint32_t>::max(), uint32_t seed = 0) {
    std::mt19937 rng{ seed ? seed : std::random_device{}() };
    std::uniform_int_distribution<uint32_t> dist(0, max_value);
    std::vector<uint32_t> res(len);
    std::generate(std::begin(res), std::end(res), [&] { return dist(rng); });
    return res;
}

void run_tests() {
    std::cerr << "[\033[32mINFO\033[m] Handmade string..." << std::endl;
    test(std::string("abracadabra"));
    std::cerr << "[\033[32mINFO\033[m] OK." << std::endl;

    std::cerr << "[\033[32mINFO\033[m] Random string of lowercase alphabets..." << std::endl;
    test(random_lowercase_alphabet(10, 1));
    test(random_lowercase_alphabet(30, 2));
    test(random_lowercase_alphabet(30, 26));
    std::cerr << "[\033[32mINFO\033[m] OK." << std::endl;

    std::cerr << "[\033[32mINFO\033[m] Random vector of integers..." << std::endl;
    test(random_vector_of_uint32_t(10, 0));
    test(random_vector_of_uint32_t(30, 1));
    test(random_vector_of_uint32_t(30, 25));
    test(random_vector_of_uint32_t(30));
    std::cerr << "[\033[32mINFO\033[m] OK." << std::endl;
}

int main() {
    run_tests();

    std::cout << "Hello World" << std::endl;
    return 0;
}
Back to top page