src/str/hash/substr/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../util/alias/others/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | template <class mint, u32 base = 131> | ||
| 8 | class hash_substr { | ||
| 9 | static inline vec<mint> p; | ||
| 10 | vec<mint> hash; | ||
| 11 | |||
| 12 | public: | ||
| 13 | 35045 | CEXP void set(strnv s) NE { | |
| 14 | 35045 | cu32 n = (u32)s.size(); | |
| 15 |
38/38tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_2e61n1_tag>, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 13 taken 69452332 times.
✓ Branch 14 taken 33833 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<14l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 13 taken 26460912 times.
✓ Branch 14 taken 48 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<15l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 13 taken 26460912 times.
✓ Branch 14 taken 48 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<16l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 13 taken 12596146 times.
✓ Branch 14 taken 53 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<17l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 13 taken 12596146 times.
✓ Branch 14 taken 53 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<1000000007ul> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 13 taken 39057058 times.
✓ Branch 14 taken 101 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 13 taken 39057058 times.
✓ Branch 14 taken 101 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<14l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 13 taken 26460912 times.
✓ Branch 14 taken 48 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<15l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 13 taken 26460912 times.
✓ Branch 14 taken 48 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<16l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 13 taken 12596146 times.
✓ Branch 14 taken 53 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<17l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 13 taken 12596146 times.
✓ Branch 14 taken 53 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<14l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 13 taken 26460912 times.
✓ Branch 14 taken 48 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<15l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 13 taken 26460912 times.
✓ Branch 14 taken 48 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<16l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 13 taken 12596146 times.
✓ Branch 14 taken 53 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<17l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 13 taken 12596146 times.
✓ Branch 14 taken 53 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<1000000007ul> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 13 taken 39057058 times.
✓ Branch 14 taken 101 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 13 taken 39057058 times.
✓ Branch 14 taken 101 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<1000000007ul> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 13 taken 39057058 times.
✓ Branch 14 taken 101 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 13 taken 39057058 times.
✓ Branch 14 taken 101 times.
|
538172073 | for (hash.resize(1, 0), hash.reserve(n + 1); cchr c : s) hash.push_back(hash.back() * base + (u32)c + 1); |
| 16 |
32/38tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_2e61n1_tag>, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 1 taken 112 times.
✓ Branch 2 taken 33721 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<14l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 1 taken 24 times.
✓ Branch 2 taken 24 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<15l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 1 taken 24 times.
✓ Branch 2 taken 24 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<16l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 1 taken 53 times.
✗ Branch 2 not taken.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<17l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 1 taken 53 times.
✗ Branch 2 not taken.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<1000000007ul> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 1 taken 77 times.
✓ Branch 2 taken 24 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 1 taken 77 times.
✓ Branch 2 taken 24 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<14l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 1 taken 24 times.
✓ Branch 2 taken 24 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<15l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 1 taken 24 times.
✓ Branch 2 taken 24 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<16l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 1 taken 53 times.
✗ Branch 2 not taken.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<17l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 1 taken 53 times.
✗ Branch 2 not taken.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<14l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 1 taken 24 times.
✓ Branch 2 taken 24 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<15l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 1 taken 24 times.
✓ Branch 2 taken 24 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<16l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 1 taken 53 times.
✗ Branch 2 not taken.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<17l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 1 taken 53 times.
✗ Branch 2 not taken.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<1000000007ul> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 1 taken 77 times.
✓ Branch 2 taken 24 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 1 taken 77 times.
✓ Branch 2 taken 24 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<1000000007ul> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 1 taken 77 times.
✓ Branch 2 taken 24 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 1 taken 77 times.
✓ Branch 2 taken 24 times.
|
35045 | if (p.size() <= n) { |
| 17 |
19/38tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_2e61n1_tag>, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 2 taken 112 times.
✗ Branch 3 not taken.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<14l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<15l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<16l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 2 taken 53 times.
✗ Branch 3 not taken.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<17l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 2 taken 53 times.
✗ Branch 3 not taken.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<1000000007ul> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 2 taken 77 times.
✗ Branch 3 not taken.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 2 taken 77 times.
✗ Branch 3 not taken.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<14l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<15l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<16l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 2 taken 53 times.
✗ Branch 3 not taken.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<17l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 2 taken 53 times.
✗ Branch 3 not taken.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<14l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<15l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<16l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 2 taken 53 times.
✗ Branch 3 not taken.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<17l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 2 taken 53 times.
✗ Branch 3 not taken.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<1000000007ul> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 2 taken 77 times.
✗ Branch 3 not taken.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 2 taken 77 times.
✗ Branch 3 not taken.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<1000000007ul> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 2 taken 77 times.
✗ Branch 3 not taken.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 2 taken 77 times.
✗ Branch 3 not taken.
|
1036 | if (p.reserve(n + 1); p.empty()) p.push_back(1); |
| 18 |
38/38tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_2e61n1_tag>, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 5 taken 25850012 times.
✓ Branch 6 taken 112 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<14l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 5 taken 13230456 times.
✓ Branch 6 taken 24 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<15l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 5 taken 13230456 times.
✓ Branch 6 taken 24 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<16l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 5 taken 12596146 times.
✓ Branch 6 taken 53 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<17l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 5 taken 12596146 times.
✓ Branch 6 taken 53 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<1000000007ul> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 5 taken 25826602 times.
✓ Branch 6 taken 77 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 5 taken 25826602 times.
✓ Branch 6 taken 77 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<14l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 5 taken 13230456 times.
✓ Branch 6 taken 24 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<15l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 5 taken 13230456 times.
✓ Branch 6 taken 24 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<16l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 5 taken 12596146 times.
✓ Branch 6 taken 53 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<17l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 5 taken 12596146 times.
✓ Branch 6 taken 53 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<14l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 5 taken 13230456 times.
✓ Branch 6 taken 24 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<15l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 5 taken 13230456 times.
✓ Branch 6 taken 24 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<16l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 5 taken 12596146 times.
✓ Branch 6 taken 53 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<17l> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 5 taken 12596146 times.
✓ Branch 6 taken 53 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<1000000007ul> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 5 taken 25826602 times.
✓ Branch 6 taken 77 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 5 taken 25826602 times.
✓ Branch 6 taken 77 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<1000000007ul> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 5 taken 25826602 times.
✓ Branch 6 taken 77 times.
tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, 131u>::set(std::basic_string_view<char, std::char_traits<char> >):
✓ Branch 5 taken 25826602 times.
✓ Branch 6 taken 77 times.
|
335770272 | while (p.size() <= n) p.push_back(p.back() * base); |
| 19 | } | ||
| 20 | 35045 | } | |
| 21 | 312323032 | ND CEXP u32 size() CNE { return u32(hash.size() - 1); } | |
| 22 | 10453156558 | CEXP mint get(u32 pos, u32 len = -1_u32) CNE { | |
| 23 |
2/4✓ Branch 1 taken 832146142 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 832146142 times.
✗ Branch 5 not taken.
|
10453156558 | assert(!p.empty() && pos < hash.size()); |
| 24 | 10453156558 | return hash[pos + min(len, (u32)hash.size() - 1 - pos)] - hash[pos] * p[len]; | |
| 25 | } | ||
| 26 | }; | ||
| 27 | |||
| 28 | } // namespace tifa_libs | ||
| 29 |