src/str/manacher/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../util/alias/others/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | 24 | CEXP vecu manacher(strnv t) NE { | |
| 8 | 48 | strn s{'\001', '\002'}; | |
| 9 |
2/2✓ Branch 4 taken 6615216 times.
✓ Branch 5 taken 24 times.
|
6615240 | for (cchr c : t) (s += c) += '\002'; |
| 10 | 24 | s += '\003'; | |
| 11 | 24 | vecu p(s.size()); | |
| 12 |
2/2✓ Branch 1 taken 13230456 times.
✓ Branch 2 taken 24 times.
|
13230480 | for (u32 i = 1, j = 0; i + 1 < s.size(); ++i) { |
| 13 |
2/2✓ Branch 1 taken 13230432 times.
✓ Branch 2 taken 24 times.
|
13230456 | if (j + p[j] >= i) p[i] = min(j + p[j] - i, p[2 * j - i]); |
| 14 |
2/2✓ Branch 5 taken 13230456 times.
✓ Branch 6 taken 13230456 times.
|
26460912 | while (s[i - p[i]] == s[i + p[i]]) ++p[i]; |
| 15 |
2/2✓ Branch 2 taken 6457671 times.
✓ Branch 3 taken 6772785 times.
|
13230456 | if (i + p[i] > j + p[j]) j = i; |
| 16 | } | ||
| 17 |
2/2✓ Branch 5 taken 13230504 times.
✓ Branch 6 taken 24 times.
|
13230528 | for (auto& i : p) --i; |
| 18 | 48 | return {begin(p) + 2, end(p) - 2}; | |
| 19 | 24 | } | |
| 20 | |||
| 21 | } // namespace tifa_libs | ||
| 22 |