This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#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; }