src/str/suffix_array/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 <common_range T = strn> | ||
| 8 | class suffix_array { | ||
| 9 | T s; | ||
| 10 | |||
| 11 | public: | ||
| 12 | vecu sa, rk, height; | ||
| 13 | |||
| 14 | // s must start from 1 | ||
| 15 | 540 | CEXPE suffix_array(cT_(T) s_) NE : s(s_), sa(s.size()), rk(s.size()) { | |
| 16 | 108 | cu32 n = u32(s.size() - 1); | |
| 17 | 108 | u32 m = 0, p; | |
| 18 |
2/2✓ Branch 6 taken 34609169 times.
✓ Branch 7 taken 108 times.
|
34609277 | for (auto x : s_) m = max(m, u32(x)); |
| 19 | 540 | vecu oldrk(n + n + 1), id(n + 1), cnt(m + 1, 0); | |
| 20 |
2/2✓ Branch 3 taken 34609061 times.
✓ Branch 4 taken 108 times.
|
34609169 | flt_ (u32, i, 1, n + 1) ++cnt[rk[i] = u32(s[i])]; |
| 21 |
2/2✓ Branch 2 taken 12063 times.
✓ Branch 3 taken 108 times.
|
12171 | flt_ (u32, i, 1, m + 1) cnt[i] += cnt[i - 1]; |
| 22 |
2/2✓ Branch 3 taken 34609061 times.
✓ Branch 4 taken 108 times.
|
34609169 | for (u32 i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i; |
| 23 | 781 | for (u32 w = 1;; w *= 2, m = p) { | |
| 24 | 781 | p = 0; | |
| 25 |
2/2✓ Branch 1 taken 14680692 times.
✓ Branch 2 taken 781 times.
|
14681473 | for (u32 i = n; i > n - w; --i) id[++p] = i; |
| 26 |
2/2✓ Branch 0 taken 435151772 times.
✓ Branch 1 taken 781 times.
|
435152553 | flt_ (u32, i, 1, n + 1) |
| 27 |
2/2✓ Branch 1 taken 420471080 times.
✓ Branch 2 taken 14680692 times.
|
435151772 | if (sa[i] > w) id[++p] = sa[i] - w; |
| 28 | 781 | cnt = vecu(m + 1, 0); | |
| 29 |
2/2✓ Branch 3 taken 435151772 times.
✓ Branch 4 taken 781 times.
|
435152553 | flt_ (u32, i, 1, n + 1) ++cnt[rk[id[i]]]; |
| 30 |
2/2✓ Branch 2 taken 77108016 times.
✓ Branch 3 taken 781 times.
|
77108797 | flt_ (u32, i, 1, m + 1) cnt[i] += cnt[i - 1]; |
| 31 |
2/2✓ Branch 5 taken 435151772 times.
✓ Branch 6 taken 781 times.
|
435152553 | for (u32 i = n; i >= 1; --i) sa[cnt[rk[id[i]]]--] = id[i]; |
| 32 | 781 | copy(rk, begin(oldrk)), p = 0; | |
| 33 |
2/2✓ Branch 0 taken 435151772 times.
✓ Branch 1 taken 781 times.
|
435152553 | flt_ (u32, i, 1, n + 1) { |
| 34 | 435151772 | u32 x = sa[i], y = sa[i - 1]; | |
| 35 |
4/4✓ Branch 2 taken 358053825 times.
✓ Branch 3 taken 77097947 times.
✓ Branch 6 taken 34607067 times.
✓ Branch 7 taken 323446758 times.
|
435151772 | rk[x] = oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w] ? p : ++p; |
| 36 | } | ||
| 37 |
2/2✓ Branch 0 taken 108 times.
✓ Branch 1 taken 673 times.
|
781 | if (p == n) break; |
| 38 | } | ||
| 39 | 108 | } | |
| 40 | |||
| 41 | 28 | CEXP void get_height() NE { | |
| 42 | 28 | cu32 n = u32(s.size() - 1); | |
| 43 | 28 | height = vecu(n + 1); | |
| 44 |
2/2✓ Branch 0 taken 14528126 times.
✓ Branch 1 taken 28 times.
|
14528154 | for (u32 i = 1, k = 0; i <= n; ++i) { |
| 45 |
2/2✓ Branch 1 taken 28 times.
✓ Branch 2 taken 14528098 times.
|
14528126 | if (rk[i] == 1) continue; |
| 46 |
2/2✓ Branch 0 taken 14527942 times.
✓ Branch 1 taken 156 times.
|
14528098 | if (k) --k; |
| 47 |
5/6✓ Branch 0 taken 29056040 times.
✗ Branch 1 not taken.
✓ Branch 6 taken 14527942 times.
✓ Branch 7 taken 14528098 times.
✓ Branch 8 taken 14527942 times.
✓ Branch 9 taken 14528098 times.
|
29056040 | while (i + k <= n && s[i + k] == s[sa[rk[i] - 1] + k]) ++k; |
| 48 | 14528098 | height[rk[i]] = k; | |
| 49 | } | ||
| 50 | 28 | } | |
| 51 | // s.substr(begs) := s[begs..s.size() - 1] | ||
| 52 | // -1: t > s.substr | ||
| 53 | // 0 : t == s.substr | ||
| 54 | // 1 : t < s.substr, t is a prefix of s.substr | ||
| 55 | // 2 : t < s.substr, t isn't prefix of s.substr | ||
| 56 | 2790959 | ND CEXP i32 compare_substr(T t, u32 begs = 1, u32 begt = 1) CNE { | |
| 57 |
6/6✓ Branch 1 taken 779531770 times.
✓ Branch 2 taken 89298 times.
✓ Branch 4 taken 778955047 times.
✓ Branch 5 taken 576723 times.
✓ Branch 6 taken 778955047 times.
✓ Branch 7 taken 666021 times.
|
779621068 | while (begs < s.size() && begt < t.size()) { |
| 58 |
2/2✓ Branch 2 taken 1266612 times.
✓ Branch 3 taken 777688435 times.
|
778955047 | if (t[begt] > s[begs]) return -1; |
| 59 |
2/2✓ Branch 2 taken 858326 times.
✓ Branch 3 taken 776830109 times.
|
777688435 | if (t[begt] < s[begs]) return 2; |
| 60 | 776830109 | ++begs, ++begt; | |
| 61 | } | ||
| 62 |
6/6✓ Branch 1 taken 89298 times.
✓ Branch 2 taken 576723 times.
✓ Branch 4 taken 19056 times.
✓ Branch 5 taken 70242 times.
✓ Branch 6 taken 19056 times.
✓ Branch 7 taken 646965 times.
|
666021 | if (begs == s.size() && begt == t.size()) return 0; |
| 63 |
2/2✓ Branch 1 taken 576723 times.
✓ Branch 2 taken 70242 times.
|
646965 | retif_((begt >= t.size()), 1, -1); |
| 64 | } | ||
| 65 | // the smallest rank of suffix that is greater than or equal t | ||
| 66 | 73292 | ND CEXP u32 lower_bound(T t) CNE { | |
| 67 | 73292 | u32 l = 1, r = u32(s.size() - 1), ret = u32(s.size()); | |
| 68 |
2/2✓ Branch 0 taken 1393765 times.
✓ Branch 1 taken 73292 times.
|
1467057 | while (r >= l) { |
| 69 | 1393765 | cu32 m = l + (r - l) / 2; | |
| 70 |
2/2✓ Branch 4 taken 707193 times.
✓ Branch 5 taken 686572 times.
|
1393765 | if (compare_substr(t, sa[m]) < 0) l = m + 1; |
| 71 | 686572 | else r = m - 1, ret = m; | |
| 72 | } | ||
| 73 | 73292 | return ret; | |
| 74 | } | ||
| 75 | // the smallest rank of suffix that is greater than t and t isn't prefix of that | ||
| 76 | 73292 | ND CEXP u32 upper_bound(T t) CNE { | |
| 77 | 73292 | u32 l = 1, r = u32(s.size() - 1), ret = u32(s.size()); | |
| 78 |
2/2✓ Branch 0 taken 1397194 times.
✓ Branch 1 taken 73292 times.
|
1470486 | while (r >= l) |
| 79 |
2/2✓ Branch 4 taken 954228 times.
✓ Branch 5 taken 442966 times.
|
1397194 | if (cu32 m = l + (r - l) / 2; compare_substr(t, sa[m]) <= 1) l = m + 1; |
| 80 | 442966 | else r = m - 1, ret = m; | |
| 81 | 73292 | return ret; | |
| 82 | } | ||
| 83 | 73292 | ND CEXP u32 frequency(T t) CNE { return upper_bound(t) - lower_bound(t); } | |
| 84 | }; | ||
| 85 | |||
| 86 | } // namespace tifa_libs | ||
| 87 |