src/str/lcs_sa/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../suffix_array/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | // @return {sl, sr, tl, tr} s.t. s[sl..sr-1] == t[tl..tr-1] | ||
| 8 | 28 | CEXP pt4u lcs_sa(strnv s, strnv t) NE { | |
| 9 | 28 | tifa_libs::suffix_array sa(" "s + s.data() + "#" + t.data()); | |
| 10 | 28 | sa.get_height(); | |
| 11 | 28 | pt3u ans{}; | |
| 12 |
2/2✓ Branch 1 taken 14528098 times.
✓ Branch 2 taken 28 times.
|
14528126 | flt_ (u32, i, 2, (u32)sa.sa.size()) { |
| 13 |
6/6✓ Branch 2 taken 7308288 times.
✓ Branch 3 taken 7219810 times.
✓ Branch 6 taken 4999952 times.
✓ Branch 7 taken 2308336 times.
✓ Branch 8 taken 4999952 times.
✓ Branch 9 taken 9528146 times.
|
14528098 | if (sa.sa[i - 1] - 1 < s.size() && sa.sa[i] - 1 > s.size()) ans = max(ans, pt3u{sa.height[i], sa.sa[i - 1] - 1, sa.sa[i] - 1}); |
| 14 |
6/6✓ Branch 2 taken 7308296 times.
✓ Branch 3 taken 7219802 times.
✓ Branch 6 taken 4999942 times.
✓ Branch 7 taken 2308354 times.
✓ Branch 8 taken 4999942 times.
✓ Branch 9 taken 9528156 times.
|
14528098 | if (sa.sa[i] - 1 < s.size() && sa.sa[i - 1] - 1 > s.size()) ans = max(ans, pt3u{sa.height[i], sa.sa[i] - 1, sa.sa[i - 1] - 1}); |
| 15 | } | ||
| 16 | 28 | auto [l, a, b] = ans; | |
| 17 | 28 | b -= (u32)s.size() + 1; | |
| 18 |
2/2✓ Branch 0 taken 27 times.
✓ Branch 1 taken 1 time.
|
28 | if (l) return {a, a + l, b, b + l}; |
| 19 | 1 | return {0, 0, 0, 0}; | |
| 20 | 28 | } | |
| 21 | |||
| 22 | } // namespace tifa_libs | ||
| 23 |