Gusfield (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 pre-processes and stores the string and the reverse of the string, 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
1997