GCC Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 100.0% 49 / 0 / 49
Functions: 100.0% 7 / 0 / 7
Branches: 83.3% 35 / 0 / 42
src/str/hash/lcsf/lib.hpp
Line Branch Exec Source
1 #pragma once
2
3 #include "../../../util/alias/num/lib.hpp"
4
5 namespace tifa_libs {
6
7 // @return length of longest common suffix of prefixes a[0, i) and b[0, j)
8 template <class hashstr_t>
9 17512866 CEXP u32 lcsf_hash(hashstr_t CR a, hashstr_t CR b, u32 i, u32 j, u32 lmax = 0) NE {
10
7/14
unsigned int tifa_libs::lcsf_hash<tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<16l> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<17l> >, 131u> >(tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<16l> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<17l> >, 131u> const&, tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<16l> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<17l> >, 131u> const&, unsigned int, unsigned int, unsigned int):
✗ Branch 0 not taken.
✓ Branch 1 taken 2501838 times.
unsigned int tifa_libs::lcsf_hash<tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<1000000007ul> >, 131u> >(tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<1000000007ul> >, 131u> const&, tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<1000000007ul> >, 131u> const&, unsigned int, unsigned int, unsigned int):
✗ Branch 0 not taken.
✓ Branch 1 taken 2501838 times.
unsigned int tifa_libs::lcsf_hash<tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<16l> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<17l> >, 131u> >(tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<16l> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<17l> >, 131u> const&, tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<16l> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<17l> >, 131u> const&, unsigned int, unsigned int, unsigned int):
✗ Branch 0 not taken.
✓ Branch 1 taken 2501838 times.
unsigned int tifa_libs::lcsf_hash<tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<16l> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<17l> >, 131u> >(tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<16l> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<17l> >, 131u> const&, tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<16l> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<17l> >, 131u> const&, unsigned int, unsigned int, unsigned int):
✗ Branch 0 not taken.
✓ Branch 1 taken 2501838 times.
unsigned int tifa_libs::lcsf_hash<tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<1000000007ul> >, 131u> >(tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<1000000007ul> >, 131u> const&, tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<1000000007ul> >, 131u> const&, unsigned int, unsigned int, unsigned int):
✗ Branch 0 not taken.
✓ Branch 1 taken 2501838 times.
unsigned int tifa_libs::lcsf_hash<tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<1000000007ul> >, 131u> >(tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<1000000007ul> >, 131u> const&, tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<1000000007ul> >, 131u> const&, unsigned int, unsigned int, unsigned int):
✗ Branch 0 not taken.
✓ Branch 1 taken 2501838 times.
unsigned int tifa_libs::lcsf_hash<tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_2e61n1_tag>, 131u> >(tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_2e61n1_tag>, 131u> const&, tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_2e61n1_tag>, 131u> const&, unsigned int, unsigned int, unsigned int):
✗ Branch 0 not taken.
✓ Branch 1 taken 2501838 times.
 17512866 if (!lmax) lmax = (u32)max(a.size(), b.size());
11 17512866 u32 l = 0, r = min({lmax, i, j}) + 1;
12
14/14
unsigned int tifa_libs::lcsf_hash<tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<16l> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<17l> >, 131u> >(tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<16l> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<17l> >, 131u> const&, tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<16l> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<17l> >, 131u> const&, unsigned int, unsigned int, unsigned int):
✓ Branch 0 taken 3475455 times.
✓ Branch 1 taken 2501838 times.
unsigned int tifa_libs::lcsf_hash<tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<1000000007ul> >, 131u> >(tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<1000000007ul> >, 131u> const&, tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<1000000007ul> >, 131u> const&, unsigned int, unsigned int, unsigned int):
✓ Branch 0 taken 3475455 times.
✓ Branch 1 taken 2501838 times.
unsigned int tifa_libs::lcsf_hash<tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<16l> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<17l> >, 131u> >(tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<16l> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<17l> >, 131u> const&, tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<16l> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<17l> >, 131u> const&, unsigned int, unsigned int, unsigned int):
✓ Branch 0 taken 3475455 times.
✓ Branch 1 taken 2501838 times.
unsigned int tifa_libs::lcsf_hash<tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<16l> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<17l> >, 131u> >(tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<16l> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<17l> >, 131u> const&, tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<16l> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<17l> >, 131u> const&, unsigned int, unsigned int, unsigned int):
✓ Branch 0 taken 3475455 times.
✓ Branch 1 taken 2501838 times.
unsigned int tifa_libs::lcsf_hash<tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<1000000007ul> >, 131u> >(tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<1000000007ul> >, 131u> const&, tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<1000000007ul> >, 131u> const&, unsigned int, unsigned int, unsigned int):
✓ Branch 0 taken 3475455 times.
✓ Branch 1 taken 2501838 times.
unsigned int tifa_libs::lcsf_hash<tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<1000000007ul> >, 131u> >(tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<1000000007ul> >, 131u> const&, tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<1000000007ul> >, 131u> const&, unsigned int, unsigned int, unsigned int):
✓ Branch 0 taken 3475455 times.
✓ Branch 1 taken 2501838 times.
unsigned int tifa_libs::lcsf_hash<tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_2e61n1_tag>, 131u> >(tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_2e61n1_tag>, 131u> const&, tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_2e61n1_tag>, 131u> const&, unsigned int, unsigned int, unsigned int):
✓ Branch 0 taken 3475455 times.
✓ Branch 1 taken 2501838 times.
 41841051 while (l + 1 < r) {
13 24328185 cu32 m = (l + r) / 2;
14
14/14
unsigned int tifa_libs::lcsf_hash<tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<16l> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<17l> >, 131u> >(tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<16l> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<17l> >, 131u> const&, tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<16l> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<17l> >, 131u> const&, unsigned int, unsigned int, unsigned int):
✓ Branch 3 taken 3012011 times.
✓ Branch 4 taken 463444 times.
unsigned int tifa_libs::lcsf_hash<tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<1000000007ul> >, 131u> >(tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<1000000007ul> >, 131u> const&, tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<1000000007ul> >, 131u> const&, unsigned int, unsigned int, unsigned int):
✓ Branch 3 taken 3012011 times.
✓ Branch 4 taken 463444 times.
unsigned int tifa_libs::lcsf_hash<tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<16l> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<17l> >, 131u> >(tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<16l> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<17l> >, 131u> const&, tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<16l> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<17l> >, 131u> const&, unsigned int, unsigned int, unsigned int):
✓ Branch 3 taken 3012011 times.
✓ Branch 4 taken 463444 times.
unsigned int tifa_libs::lcsf_hash<tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<16l> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<17l> >, 131u> >(tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<16l> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<17l> >, 131u> const&, tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<16l> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<17l> >, 131u> const&, unsigned int, unsigned int, unsigned int):
✓ Branch 3 taken 3012011 times.
✓ Branch 4 taken 463444 times.
unsigned int tifa_libs::lcsf_hash<tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<1000000007ul> >, 131u> >(tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<1000000007ul> >, 131u> const&, tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<1000000007ul> >, 131u> const&, unsigned int, unsigned int, unsigned int):
✓ Branch 3 taken 3012011 times.
✓ Branch 4 taken 463444 times.
unsigned int tifa_libs::lcsf_hash<tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<1000000007ul> >, 131u> >(tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<1000000007ul> >, 131u> const&, tifa_libs::hash_substr2<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<1000000007ul> >, 131u> const&, unsigned int, unsigned int, unsigned int):
✓ Branch 3 taken 3012011 times.
✓ Branch 4 taken 463444 times.
unsigned int tifa_libs::lcsf_hash<tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_2e61n1_tag>, 131u> >(tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_2e61n1_tag>, 131u> const&, tifa_libs::hash_substr<tifa_libs::mint_impl_::mint<tifa_libs::mint_2e61n1_tag>, 131u> const&, unsigned int, unsigned int, unsigned int):
✓ Branch 3 taken 3012011 times.
✓ Branch 4 taken 463444 times.
 24328185 (a.get(i - m, m) == b.get(j - m, m) ? l : r) = m;
15 }
16 17512866 return l;
17 }
18
19 } // namespace tifa_libs
20