seq/manacher.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include <vector> | ||
| 4 | #include <cassert> | ||
| 5 | |||
| 6 | namespace wala { | ||
| 7 | |||
| 8 | /** | ||
| 9 | * manacher(S): return the maximum palindromic substring of S centered at each point | ||
| 10 | * | ||
| 11 | * Input: string (or vector) of length N (no restrictions on character-set) | ||
| 12 | * Output: vector res of length 2*N+1 | ||
| 13 | * For any 0 <= i <= 2*N: | ||
| 14 | * * i % 2 == res[i] % 2 | ||
| 15 | * * the half-open substring S[(i-res[i])/2, (i+res[i])/2) is a palindrome of length res[i] | ||
| 16 | * * For odd palindromes, take odd i, and vice versa | ||
| 17 | */ | ||
| 18 |
1/2✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 24 times.
|
24 | template <typename V> std::vector<int> manacher(const V& S) { |
| 19 | 24 | int N = int(S.size()); | |
| 20 | 24 | std::vector<int> res(2*N+1, 0); | |
| 21 |
2/2✓ Branch 16 → 6 taken 13230408 times.
✓ Branch 16 → 17 taken 24 times.
|
13230432 | for (int i = 1, j = -1, r = 0; i < 2*N; i++, j--) { |
| 22 |
2/2✓ Branch 6 → 7 taken 3793389 times.
✓ Branch 6 → 8 taken 9437019 times.
|
13230408 | if (i > r) { |
| 23 | 3793389 | r = i+1, res[i] = 1; | |
| 24 | } else { | ||
| 25 | 9437019 | res[i] = res[j]; | |
| 26 | } | ||
| 27 |
2/2✓ Branch 9 → 10 taken 13054619 times.
✓ Branch 9 → 15 taken 175789 times.
|
13230408 | if (i+res[i] >= r) { |
| 28 | 13054619 | int b = r>>1, a = i-b; | |
| 29 |
4/4✓ Branch 11 → 12 taken 10876399 times.
✓ Branch 11 → 14 taken 5000047 times.
✓ Branch 12 → 13 taken 2821827 times.
✓ Branch 12 → 14 taken 8054572 times.
|
15876446 | while (a > 0 && b < N && S[a-1] == S[b]) { |
| 30 | 2821827 | a--, b++; | |
| 31 | } | ||
| 32 | 13054619 | res[i] = b-a, j = i, r = b<<1; | |
| 33 | } | ||
| 34 | } | ||
| 35 | 24 | return res; | |
| 36 | } | ||
| 37 | |||
| 38 | /** | ||
| 39 | * manacher_odd(S): return the maximum palindromic substring of S centered at each point | ||
| 40 | * | ||
| 41 | * Input: string (or vector) of length N (no restrictions on character-set) | ||
| 42 | * Output: vector res of length N | ||
| 43 | * For any 0 <= i < N: | ||
| 44 | * * the half-open substring S[i-res[i], i+res[i]] is a palindrome of length 2*res[i]+1 | ||
| 45 | */ | ||
| 46 | ✗ | template <typename V> std::vector<int> manacher_odd(const V& S) { | |
| 47 | ✗ | int N = int(S.size()); | |
| 48 | ✗ | std::vector<int> res(N); | |
| 49 | ✗ | for (int i = 1, j = -1, r = 0; i < N; i++, j--) { | |
| 50 | ✗ | if (i > r) { | |
| 51 | ✗ | r = i, res[i] = 0; | |
| 52 | } else { | ||
| 53 | ✗ | res[i] = res[j]; | |
| 54 | } | ||
| 55 | ✗ | if (i+res[i] >= r) { | |
| 56 | ✗ | int b = r, a = 2*i-r; | |
| 57 | ✗ | while (a-1 >= 0 && b+1 < N && S[a-1] == S[b+1]) { | |
| 58 | ✗ | a--, b++; | |
| 59 | } | ||
| 60 | ✗ | res[i] = b-i, j = i, r = b; | |
| 61 | } | ||
| 62 | } | ||
| 63 | ✗ | return res; | |
| 64 | } | ||
| 65 | |||
| 66 | } // namespace wala | ||
| 67 |