Manacher (Longest Palindromic Substring Longest Palindromic Substring)

From Algorithm Wiki
Revision as of 07:57, 10 April 2023 by Admin (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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

Reference

https://doi.org/10.1145%2F321892.321896

Retrieved from "https://algorithm-wiki.csail.mit.edu/w/index.php?title=Manacher_(Longest_Palindromic_Substring_Longest_Palindromic_Substring)&oldid=47041"