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: 100.0% 42 / 0 / 42
src/str/hash/lcpf/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 prefix of suffixes a[i, a.size()) and b[j, b.size())
8 template <class hashstr_t>
9 90980043 CEXP u32 lcpf_hash(hashstr_t CR a, hashstr_t CR b, u32 i, u32 j, u32 lmax = 0) NE {
10
14/14
unsigned int tifa_libs::lcpf_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 9311639 times.
✓ Branch 1 taken 3685510 times.
unsigned int tifa_libs::lcpf_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 9311639 times.
✓ Branch 1 taken 3685510 times.
unsigned int tifa_libs::lcpf_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 9311639 times.
✓ Branch 1 taken 3685510 times.
unsigned int tifa_libs::lcpf_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 9311639 times.
✓ Branch 1 taken 3685510 times.
unsigned int tifa_libs::lcpf_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 9311639 times.
✓ Branch 1 taken 3685510 times.
unsigned int tifa_libs::lcpf_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 9311639 times.
✓ Branch 1 taken 3685510 times.
unsigned int tifa_libs::lcpf_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 9311639 times.
✓ Branch 1 taken 3685510 times.
 90980043 if (!lmax) lmax = (u32)max(a.size(), b.size());
11 90980043 u32 l = 0, r = min({lmax, a.size() - i, b.size() - j}) + 1;
12
14/14
unsigned int tifa_libs::lcpf_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 167523375 times.
✓ Branch 1 taken 12997149 times.
unsigned int tifa_libs::lcpf_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 167523375 times.
✓ Branch 1 taken 12997149 times.
unsigned int tifa_libs::lcpf_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 167523375 times.
✓ Branch 1 taken 12997149 times.
unsigned int tifa_libs::lcpf_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 167523375 times.
✓ Branch 1 taken 12997149 times.
unsigned int tifa_libs::lcpf_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 167523375 times.
✓ Branch 1 taken 12997149 times.
unsigned int tifa_libs::lcpf_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 167523375 times.
✓ Branch 1 taken 12997149 times.
unsigned int tifa_libs::lcpf_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 167523375 times.
✓ Branch 1 taken 12997149 times.
 1263643668 while (l + 1 < r) {
13 1172663625 cu32 m = (l + r) / 2;
14
14/14
unsigned int tifa_libs::lcpf_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 51124319 times.
✓ Branch 4 taken 116399056 times.
unsigned int tifa_libs::lcpf_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 51124319 times.
✓ Branch 4 taken 116399056 times.
unsigned int tifa_libs::lcpf_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 51124319 times.
✓ Branch 4 taken 116399056 times.
unsigned int tifa_libs::lcpf_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 51124319 times.
✓ Branch 4 taken 116399056 times.
unsigned int tifa_libs::lcpf_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 51124319 times.
✓ Branch 4 taken 116399056 times.
unsigned int tifa_libs::lcpf_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 51124319 times.
✓ Branch 4 taken 116399056 times.
unsigned int tifa_libs::lcpf_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 51124319 times.
✓ Branch 4 taken 116399056 times.
 1172663625 (a.get(i, m) == b.get(j, m) ? l : r) = m;
15 }
16 90980043 return l;
17 }
18
19 } // namespace tifa_libs
20