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

Pareto Decades graph