Longest Palindromic Substring: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
No edit summary
No edit summary
Line 36: Line 36:
[[File:Longest Palindromic Substring - Space.png|1000px]]
[[File:Longest Palindromic Substring - Space.png|1000px]]


== Pareto Frontier Improvements Graph ==  
== Time-Space Tradeoff ==  


[[File:Longest Palindromic Substring - Pareto Frontier.png|1000px]]
[[File:Longest Palindromic Substring - Pareto Frontier.png|1000px]]

Revision as of 14:46, 15 February 2023

Description

Given a string of length $n$, find the palindromic substrings of maximal length.

Parameters

n: length of given string

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Naive 1940 $O(n^{3})$ $O({1})$ auxiliary Exact Deterministic Space
Dynamic Programming 1953 $O(n^{2})$ $O(n^{2})$ Exact Deterministic Space
Manacher 1975 $O(n)$ $O(n)$ auxiliary Exact Deterministic Time
Jeuring 1994 $O(n)$ $O(n)$ auxiliary? Exact Deterministic Time
Gusfield 1997 $O(n)$ $O(n)$ auxiliary Exact Deterministic Time

Time Complexity Graph

Error creating thumbnail: Unable to save thumbnail to destination

Space Complexity Graph

Error creating thumbnail: Unable to save thumbnail to destination

Time-Space Tradeoff

Error creating thumbnail: Unable to save thumbnail to destination