|
The longest palindromic substring problem should not be confused with the different problem of finding the longest palindromic [[subsequence]].
// yes
==Slow algorithm==
This algorithm is slower than Manacher's algorithm, but is a good stepping stone for understanding Manacher's algorithm. It looks at each character as the center of a palindrome and loops to determine the largest palindrome with that center.
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|".
Longest_Palindrome_SLOW(string S) {
string S' = S with a bogus character (eg. '|') inserted between each character (including outer boundaries)
array PalindromeRadii = [0,...,0] // The radius of the longest palindrome centered on each place in S'
// note: length(S') = length(PalindromeRadii) = 2 × length(S) + 1
Center = 0
'''while''' Center < length(S') '''{'''
// Determine the longest palindrome starting at Center-Radius and going to Center+Radius
Radius = 0
'''while''' Center-(Radius+1) >= 0 '''and''' Center+(Radius+1) < length(S') '''and''' S'[Center-(Radius+1)] = S'[Center+(Radius+1)] '''{'''
Radius = Radius+1
'''}'''
// Save the radius of the longest palindrome in the array
PalindromeRadii[Center] = Radius
Center = Center+1
'''}'''
longest_palindrome_in_S' = 2*max(PalindromeRadii)+1
longest_palindrome_in_S = (longest_palindrome_in_S'-1)/2
'''return''' longest_palindrome_in_S
}
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.
==Manacher's algorithm==
| 