Longest Palindromic Substring: Difference between revisions

Revision as of 14:46, 15 February 2023

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

n: length of given string

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

@@ Line 36: / Line 36: @@
 [[File:Longest Palindromic Substring - Space.png|1000px]]
-== Pareto Frontier Improvements Graph ==
+== Time-Space Tradeoff ==
 [[File:Longest Palindromic Substring - Pareto Frontier.png|1000px]]