Expanding a palindrome around every centre takes O(n²) in the worst case. Manacher’s algorithm notices that inside a palindrome the right half mirrors the left, so a centre on the right can start from its mirror’s radius instead of from zero.
- Average time
- O(n)
- Space
- O(n)