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".
-time algorithm for listing all the palindromes that appear at the start of a given string of length
However, as observed e.g., by Apostolico, Breslauer & Galil (1995), the same algorithm can also be used to find all maximal palindromic substrings anywhere within the input string, again in
-time solution to the longest palindromic substring problem.
A faster algorithm can be achieved in the word RAM model of computation if the size
[2] The longest palindromic substring problem should not be confused with the different problem of finding the longest palindromic subsequence.
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.
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".
There are some special cases to consider, but that trick speeds up the computation dramatically.
[citation needed] Manacher's algorithm is faster because it reuses precomputed data when a palindrome exists inside another palindrome.
In this situation, the palindrome at Center will have the same length as the one at MirroredCenter.
That is, it extends "to the left" (or, contains characters with a lower index than any inside the "Old" palindrome).
For example, if the string was "ababc", the "Old" palindrome could be "bab" with the Center being the second "b" and the MirroredCenter being the first "b".
An example string would be "abcbpbcbp" where the "Old" palindrome is "bcbpbcb" and the Center is on the second "c".
The longest palindrome at the Center on the second "c" has to be at least that long and, in this case, is longer.
This can be seen by noting that Center strictly increases after each outer loop and the sum Center + Radius is non-decreasing.
Moreover, the number of operations in the first inner loop is linear in the increase of the sum Center + Radius while the number of operations in the second inner loop is linear in the increase of Center.
Since Center ≤ 2n+1 and Radius ≤ n, the total number of operations in the first and second inner loops is