Longest Palindromic Substring (Longest Palindromic Substring)

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

Space Complexity Graph

Time-Space Tradeoff