Longest Palindromic Substring: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
No edit summary
No edit summary
Line 6: Line 6:
== Parameters ==  
== Parameters ==  


n: length of given string
$n$: length of given string


== Table of Algorithms ==  
== Table of Algorithms ==  
Line 16: Line 16:
|-
|-


| [[Naive (Longest Palindromic Substring Longest Palindromic Substring)|Naive]] || 1940 || $O(n^{3})$ || $O({1})$ auxiliary || Exact || Deterministic || [https://www.geeksforgeeks.org/longest-palindrome-substring-set-1/ Space]
| [[Naive (Longest Palindromic Substring Longest Palindromic Substring)|Naive]] || 1940 || $O(n^{3})$ || $O({1})$ || Exact || Deterministic || [https://www.geeksforgeeks.org/longest-palindrome-substring-set-1/ Space]
|-
|-
| [[Dynamic Programming (Longest Palindromic Substring Longest Palindromic Substring)|Dynamic Programming]] || 1953 || $O(n^{2})$ || $O(n^{2})$ || Exact || Deterministic || [https://www.geeksforgeeks.org/longest-palindrome-substring-set-1/ Space]
| [[Dynamic Programming (Longest Palindromic Substring Longest Palindromic Substring)|Dynamic Programming]] || 1953 || $O(n^{2})$ || $O(n^{2})$ || Exact || Deterministic || [https://www.geeksforgeeks.org/longest-palindrome-substring-set-1/ Space]
|-
|-
| [[Manacher (Longest Palindromic Substring Longest Palindromic Substring)|Manacher]] || 1975 || $O(n)$ || $O(n)$ auxiliary || Exact || Deterministic || [https://doi.org/10.1145%2F321892.321896 Time]
| [[Manacher (Longest Palindromic Substring Longest Palindromic Substring)|Manacher]] || 1975 || $O(n)$ || $O(n)$ || Exact || Deterministic || [https://doi.org/10.1145%2F321892.321896 Time]
|-
|-
| [[Jeuring (Longest Palindromic Substring Longest Palindromic Substring)|Jeuring]] || 1994 || $O(n)$ || $O(n)$ auxiliary? || Exact || Deterministic || [https://doi.org/10.1007%2FBF01182773 Time]
| [[Jeuring (Longest Palindromic Substring Longest Palindromic Substring)|Jeuring]] || 1994 || $O(n)$ || $O(n)$? || Exact || Deterministic || [https://doi.org/10.1007%2FBF01182773 Time]
|-
|-
| [[Gusfield  (Longest Palindromic Substring Longest Palindromic Substring)|Gusfield ]] || 1997 || $O(n)$ || $O(n)$ auxiliary || Exact || Deterministic || [https://www.cambridge.org/core/books/algorithms-on-strings-trees-and-sequences/F0B095049C7E6EF5356F0A26686C20D3 Time]
| [[Gusfield  (Longest Palindromic Substring Longest Palindromic Substring)|Gusfield ]] || 1997 || $O(n)$ || $O(n)$ || Exact || Deterministic || [https://www.cambridge.org/core/books/algorithms-on-strings-trees-and-sequences/F0B095049C7E6EF5356F0A26686C20D3 Time]
|-
|-
|}
|}

Revision as of 08:23, 10 April 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})$ 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

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