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})$	Exact	Deterministic	Space
Dynamic Programming	1953	$O(n^{2})$	$O(n^{2})$	Exact	Deterministic	Space
Manacher	1975	$O(n)$	$O(n)$	Exact	Deterministic	Time
Jeuring	1994	$O(n)$	$O(n)$?	Exact	Deterministic	Time
Gusfield	1997	$O(n)$	$O(n)$	Exact	Deterministic	Time

Time Complexity Graph