Manacher (Longest Palindromic Substring Longest Palindromic Substring): Difference between revisions
Jump to navigation
Jump to search
(Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ auxiliary 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.ezproxy.canberra.edu.au/10.1145%2F321892.321896") |
No edit summary |
||
| Line 5: | Line 5: | ||
== Space Complexity == | == Space Complexity == | ||
$O(n)$ | $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.) | (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.) | ||
Latest revision as of 08:57, 10 April 2023
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.ezproxy.canberra.edu.au/10.1145%2F321892.321896