src/math/debruijn/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../util/alias/others/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | // Given alphabet $[0,k)$ constructs a cyclic string of length $k^n$ that contains every length $n$ string as substr | ||
| 8 | 5 | CEXP vecu deBruijn(u32 n, u32 k, u32 maxsz = 0) NE { | |
| 9 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 5 times.
|
5 | retif_((k == 1) [[unlikely]], {0}); |
| 10 |
1/2✓ Branch 0 taken 5 times.
✗ Branch 1 not taken.
|
5 | if (!maxsz) { |
| 11 | 5 | maxsz = 1; | |
| 12 |
2/2✓ Branch 0 taken 31 times.
✓ Branch 1 taken 5 times.
|
36 | flt_ (u32, i, 0, n) maxsz *= k; |
| 13 | } | ||
| 14 | 10 | vecu ret, _(n + 1); | |
| 15 | 8696 | auto f = [&](auto&& f, u32 t, u32 p) NE -> void { | |
| 16 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 8696 times.
|
8696 | if (ret.size() >= maxsz) return; |
| 17 |
2/2✓ Branch 0 taken 5925 times.
✓ Branch 1 taken 2771 times.
|
8696 | if (t > n) { |
| 18 |
2/2✓ Branch 0 taken 4457 times.
✓ Branch 1 taken 1468 times.
|
5925 | if (!(n % p)) |
| 19 |
2/2✓ Branch 2 taken 24180 times.
✓ Branch 3 taken 4457 times.
|
28637 | flt_ (u32, i, 1, p + 1) ret.push_back(_[i]); |
| 20 |
2/2✓ Branch 1 taken 5 times.
✓ Branch 2 taken 5920 times.
|
5925 | if (ret.size() >= maxsz) return; |
| 21 | } else { | ||
| 22 |
1/2✗ Branch 3 not taken.
✓ Branch 4 taken 2771 times.
|
2771 | if (_[t] = _[t - p]; ret.size() >= maxsz) return; |
| 23 | 2771 | f(f, t + 1, p); | |
| 24 |
2/2✓ Branch 1 taken 5920 times.
✓ Branch 2 taken 2771 times.
|
8691 | while (++_[t] < k) { |
| 25 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 5920 times.
|
5920 | if (ret.size() >= maxsz) return; |
| 26 | 5920 | f(f, t + 1, t); | |
| 27 | } | ||
| 28 | } | ||
| 29 | 5 | }; | |
| 30 | 5 | f(f, 1, 1), ret.resize(maxsz); | |
| 31 | 5 | return ret; | |
| 32 | 5 | } | |
| 33 | |||
| 34 | } // namespace tifa_libs | ||
| 35 |