src/str/suffix_automaton/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../util/alias/others/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | template <u32 SZ = 26> | ||
| 7 | class suffix_automaton { | ||
| 8 | // super root is 0 | ||
| 9 | u32 last{0}; | ||
| 10 | struct TIFA { | ||
| 11 | u32 len, link; | ||
| 12 | arr<u32, SZ> nex{}; | ||
| 13 | u64 sz; // app 1 | ||
| 14 | u32 times; // app 2 | ||
| 15 | bool is_clone; // app 3 | ||
| 16 | u32 firstpos; // app 3 | ||
| 17 | }; | ||
| 18 | static CEXP u8 base = 'a'; | ||
| 19 | |||
| 20 | public: | ||
| 21 | u32 sz{1}; | ||
| 22 | vec<TIFA> st; | ||
| 23 | vvecu e; | ||
| 24 | |||
| 25 | 72 | CEXP suffix_automaton() NE : st(1) { st[0].len = 0, st[0].link = -1u; } | |
| 26 | |||
| 27 | 8550784 | CEXP void extend(u32 c) NE { | |
| 28 | 8550784 | cu32 cur = sz++; | |
| 29 | 8550784 | st.emplace_back(), st[cur].len = st[last].len + 1; | |
| 30 | 8550784 | st[cur].times = 1; // app 2 | |
| 31 | 8550784 | st[cur].firstpos = st[cur].len - 1; // app 3 | |
| 32 | 8550784 | u32 p = last; | |
| 33 |
6/6✓ Branch 3 taken 21128036 times.
✓ Branch 4 taken 299 times.
✓ Branch 7 taken 12577551 times.
✓ Branch 8 taken 8550485 times.
✓ Branch 9 taken 12577551 times.
✓ Branch 10 taken 8550784 times.
|
21128335 | while (~p && !st[p].nex[c]) st[p].nex[c] = cur, p = st[p].link; |
| 34 |
2/2✓ Branch 0 taken 299 times.
✓ Branch 1 taken 8550485 times.
|
8550784 | if (!~p) st[cur].link = 0; |
| 35 | else { | ||
| 36 | 8550485 | cu32 q = st[p].nex[c]; | |
| 37 |
2/2✓ Branch 2 taken 6022178 times.
✓ Branch 3 taken 2528307 times.
|
8550485 | if (st[p].len + 1 == st[q].len) st[cur].link = q; |
| 38 | else { | ||
| 39 | 2528307 | cu32 clone = sz++; | |
| 40 | 2528307 | st.emplace_back(), st[clone].nex = st[q].nex, st[clone].len = st[p].len + 1, st[clone].link = st[q].link; | |
| 41 | 2528307 | st[clone].firstpos = st[q].firstpos; // app 3 | |
| 42 | 2528307 | st[clone].is_clone = 1; // app 3 | |
| 43 |
6/6✓ Branch 3 taken 5105442 times.
✓ Branch 4 taken 267 times.
✓ Branch 7 taken 2577402 times.
✓ Branch 8 taken 2528040 times.
✓ Branch 9 taken 2577402 times.
✓ Branch 10 taken 2528307 times.
|
5105709 | while (~p && st[p].nex[c] == q) st[p].nex[c] = clone, p = st[p].link; |
| 44 | 2528307 | st[q].link = st[cur].link = clone; | |
| 45 | } | ||
| 46 | } | ||
| 47 | 8550784 | last = cur; | |
| 48 | 8550784 | } | |
| 49 | 24 | CEXP void build() NE { | |
| 50 | 24 | e = vvecu(sz); | |
| 51 | 11079091 | auto add = [&](u32 u, u32 v) NE { e[u].push_back(v); }; | |
| 52 |
2/2✓ Branch 2 taken 11079091 times.
✓ Branch 3 taken 24 times.
|
11079115 | flt_ (u32, i, 1, sz) add(u32(st[i].link), i); |
| 53 | 24 | } | |
| 54 | |||
| 55 | // app 0 | ||
| 56 | //! default: each character of t is lowercase English letters. | ||
| 57 | CEXP std::pair<u32, bool> search(strn t) NE { | ||
| 58 | u32 u = 0, i = 0; | ||
| 59 | while (i < t.size()) { | ||
| 60 | if (!st[u].nex[u32(t[i] - base)]) return {i, false}; | ||
| 61 | u = st[u].nex[u32(t[i] - base)], ++i; | ||
| 62 | } | ||
| 63 | return {u32(u), true}; | ||
| 64 | } | ||
| 65 | // app 1 | ||
| 66 | 11079115 | CEXP void getsz(u32 u = 0) NE { | |
| 67 |
2/2✓ Branch 2 taken 288056990 times.
✓ Branch 3 taken 11079115 times.
|
299136105 | for (st[u].sz = 1; auto v : st[u].nex) |
| 68 |
2/2✓ Branch 0 taken 15124405 times.
✓ Branch 1 taken 272932585 times.
|
288056990 | if (v) { |
| 69 |
2/2✓ Branch 1 taken 11079091 times.
✓ Branch 2 taken 4045314 times.
|
15124405 | if (!st[v].sz) getsz(v); |
| 70 | 15124405 | st[u].sz += st[v].sz; | |
| 71 | } | ||
| 72 | 11079115 | } | |
| 73 | // app 2 | ||
| 74 | //! need build() | ||
| 75 | CEXP void gettimes(u32 u = 0) NE { | ||
| 76 | for (auto v : e[u]) gettimes(v), st[u].times += st[v].times; | ||
| 77 | } | ||
| 78 | // app 3 | ||
| 79 | //! need build(), search() | ||
| 80 | CEXP void output_all_occurrences(u32 u, u32 P_length, vecu& ans) NE { | ||
| 81 | if (!st[u].is_clone) ans.push_back(st[u].first_pos - P_length + 1); | ||
| 82 | for (u32 v : e[u]) output_all_occurrences(v, P_length, ans); | ||
| 83 | } | ||
| 84 | // app 4 | ||
| 85 | //! default: each character of t is lowercase English letters. | ||
| 86 | CEXP pttu lcs(strnv t) NE { | ||
| 87 | u32 v = 0, len = 0, ret = 0, end = 0; | ||
| 88 | flt_ (u32, i, 0, (u32)t.size()) { | ||
| 89 | while (v && !st[v].nex[u32(t[i] - base)]) v = st[v].link, len = st[v].len; | ||
| 90 | if (st[v].nex[u32(t[i] - base)]) v = st[v].nex[u32(t[i] - base)], ++len; | ||
| 91 | if (len > ret) ret = len, end = i; | ||
| 92 | } | ||
| 93 | return {end - ret + 1, ret}; | ||
| 94 | } | ||
| 95 | }; | ||
| 96 | |||
| 97 | } // namespace tifa_libs | ||
| 98 |