Gusfield (Longest Palindromic Substring Longest Palindromic Substring)

From Algorithm Wiki
Revision as of 12:16, 15 February 2023 by Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ auxiliary 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 == Reference == https://www.cambridge.org/core/books/al...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Time Complexity

$O(n)$

Space Complexity

$O(n)$ auxiliary 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

Reference

https://www.cambridge.org/core/books/algorithms-on-strings-trees-and-sequences/F0B095049C7E6EF5356F0A26686C20D3

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