Manacher (Longest Palindromic Substring Longest Palindromic Substring)
Jump to navigation
Jump to search
Time Complexity
$O(n)$
Space Complexity
$O(n)$ words
(At the very least it stores the radii for each center, requiring O(n) space. Space usage is bounded from above by runtime, so at most O(n) space is used.)
Description
Approximate?
Exact
Randomized?
No, deterministic
Model of Computation
Word RAM
Year
1975