src/str/hash/substr_2d/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../substr/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | template <class mint, u32 base = 131, u32 base2 = 137> | ||
| 8 | class hash_substr_2d { | ||
| 9 | static inline vec<mint> p; | ||
| 10 | vec<hash_substr<mint, base>> hs; | ||
| 11 | vvec<mint> hash; | ||
| 12 | |||
| 13 | public: | ||
| 14 | 70 | CEXP void set(spn<strn> s, u32 len_c) NE { | |
| 15 | 70 | cu32 n = (u32)s.size(), m = (u32)s[0].size(); | |
| 16 |
4/6✓ Branch 0 taken 70 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 70 times.
✗ Branch 3 not taken.
✓ Branch 12 taken 35 times.
✓ Branch 13 taken 35 times.
|
210 | if (assert(0 < len_c && len_c <= m), hs.resize(n), hash = vvec<mint>(n + 1, vec<mint>(m + 1)); p.size() <= n) { |
| 17 |
1/2✓ Branch 2 taken 35 times.
✗ Branch 3 not taken.
|
35 | if (p.reserve(n + 1); p.empty()) p.push_back(1); |
| 18 |
2/2✓ Branch 5 taken 23400 times.
✓ Branch 6 taken 35 times.
|
23435 | while (p.size() <= n) p.push_back(p.back() * base2); |
| 19 | } | ||
| 20 |
2/2✓ Branch 4 taken 33732 times.
✓ Branch 5 taken 70 times.
|
33802 | flt_ (u32, i, 0, n) hs[i].set(s[i]); |
| 21 |
2/2✓ Branch 0 taken 33732 times.
✓ Branch 1 taken 70 times.
|
33802 | flt_ (u32, i, 1, n + 1) |
| 22 |
2/2✓ Branch 9 taken 30395274 times.
✓ Branch 10 taken 33732 times.
|
30429006 | flt_ (u32, j, 1, m + 1) hash[i][j] = hash[i - 1][j] * base2 + hs[i - 1].get(j - 1, len_c); |
| 23 | 70 | } | |
| 24 | ND CEXP u32 row() CNE { return u32(hash.size() - 1); } | ||
| 25 | ND CEXP u32 col() CNE { return u32(hash[0].size() - 1); } | ||
| 26 | 19662514 | CEXP mint get(u32 r, u32 c, u32 len_r = -1_u32) CNE { | |
| 27 |
3/6✓ Branch 1 taken 19662514 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 19662514 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 19662514 times.
✗ Branch 9 not taken.
|
19662514 | assert(!hs.empty() && r < hash.size() && c < hash[0].size()); |
| 28 | 19662514 | return hash[r + min(len_r, (u32)hash.size() - 1 - r)][c + 1] - hash[r][c + 1] * p[len_r]; | |
| 29 | } | ||
| 30 | }; | ||
| 31 | |||
| 32 | } // namespace tifa_libs | ||
| 33 |