Content deleted Content added
Fix radius validation for Manacher's Algorithm |
Change inconsistent highlighted source code blocks (the first one was highlighted, the second one was not) to use syntaxhighlight. Also rename the variable S' to R. |
||
| (4 intermediate revisions by 3 users not shown) | |||
Line 2:
In [[computer science]], the '''longest palindromic substring''' or '''longest symmetric factor''' problem is the problem of finding a maximum-length contiguous [[substring]] of a given string that is also a [[palindrome]]. For example, the longest palindromic substring of "bananas" is "anana". The longest palindromic substring is not guaranteed to be unique; for example, in the string "abracadabra", there is no palindromic substring with length greater than three, but there are two palindromic substrings with length three, namely, "aca" and "ada". In some applications it may be necessary to return all maximal palindromic substrings (that is, all substrings that are themselves palindromes and cannot be extended to larger palindromic substrings) rather than returning only one substring or returning the maximum length of a palindromic substring.
{{harvtxt|Manacher|1975}} invented an <math>O(n)</math>-time algorithm for listing all the palindromes that appear at the start of a given string of length <math>n</math>. However, as observed e.g., by {{harvtxt|Apostolico|Breslauer|Galil|1995}}, the same algorithm can also be used to find all maximal palindromic substrings anywhere within the input string, again in <math>O(n)</math> time. Therefore, it provides an <math>O(n)</math>-time solution to the longest palindromic substring problem. Alternative <math>O(n)</math>-time solutions were provided by {{harvtxt|Jeuring|1994}}, and by {{harvtxt|Gusfield|1997}}, who described a solution based on [[suffix tree]]s. A faster algorithm can be achieved in the [[word RAM]] model of computation if the size <math>\sigma</math> of the input alphabet is in <math>2^{o(\log n)}</math>. In particular, this algorithm runs in <math>O(n\log\sigma/\log n)</math> time using <math>O(n\log\sigma/\log n)</math> space.<ref name="CPR22">{{cite conference | last1 = Charalampopoulos | first1 = Panagiotis | last2 = Pissis | first2 = Solon P. | last3 = Radoszewski | first3 = Jakub | date = Jun 2022 | title = Longest Palindromic Substring in Sublinear Time | conference = Combinatorial Pattern Matching | editor1-last=Bannai|editor1-first=Hideo|editor2-last=Holub|editor2-first=Jan | publisher=Schloss Dagstuhl | series=Leibniz International Proceedings in Informatics (LIPIcs) | volume=223 | doi = 10.4230/LIPIcs.CPM.2022.20 | doi-access = free }} Here: Theorem 1, p.20:2.</ref> Efficient [[parallel algorithm]]s are also known for the problem.<ref>{{harvtxt|Crochemore|Rytter|1991}}, {{harvtxt|Apostolico|Breslauer|Galil|1995}}.</ref>
The longest palindromic substring problem should not be confused with the different problem of finding the longest palindromic [[subsequence]].
Line 11:
The loop at the center of the function only works for palindromes where the length is an odd number. The function works for even-length palindromes by modifying the input string. The character '|' is inserted between every character in the inputs string, and at both ends. So the input "book" becomes "|b|o|o|k|". The even-length palindrome "oo" in "book" becomes the odd-length palindrome "|o|o|".
<syntaxhighlight lang="C" line>
// C pseudocode.
Longest_Palindrome_SLOW(string S, string R) {
// R == S with a bogus character (eg. '|') inserted
// between each character (including outer boundaries)
// The radius of the longest palindrome centered on each place in R
// note: length(R) =
array
// Determine the longest palindrome
// at Center-Radius and going to Center+Radius
Radius = 0
}
</syntaxhighlight>
The runtime of this algorithm is <math>O(n^2)</math>. The outer loop runs <math>n</math> times and the inner loop can run up to <math>n/2</math> times.
Line 61 ⟶ 65:
For example, consider the input string "abacaba". By the time it gets to the "c", Manacher's algorithm will have identified the length of every palindrome centered on the letters before the "c". At the "c", it runs a loop to identify the largest palindrome centered on the "c": "abacaba". With that knowledge, everything after the "c" looks like the reflection of everything before the "c". The "a" after the "c" has the same longest palindrome as the "a" before the "c". Similarly, the "b" after the "c" has a longest palindrome that is ''at least'' the length of the longest palindrome centered on the "b" before the "c". There are some special cases to consider, but that trick speeds up the computation dramatically.{{cn|date=March 2022}}
<syntaxhighlight lang="C" line>
// C pseudocode.
Longest_Palindrome(string S, string R) {
// R == S with a bogus character (eg. '|') inserted
// between each character (including outer boundaries)
// The radius of the longest palindrome centered on each place in R
// note: length(R) =
array
Center =
Radius = 0
while Center < length( }
// A palindrome's size is equal to its radius * 2. However, since our
// variable Radius considers our bogus characters to the side of the
// center, the size of its corresponding palindrome is actually 2 *
// corresponding Radius value in PalindromeRadii
longest_palindrome_in_S = max(PalindromeRadii)
}
</syntaxhighlight>
===Special cases===
Line 197 ⟶ 204:
| year = 2022
| doi = 10.4230/LIPIcs.CPM.2022.20
| pages = 20:
}}.
*{{citation
| |||