Longest palindromic substring: Difference between revisions

Revision as of 04:42, 10 March 2023

Revision as of 07:12, 8 May 2023

Line 12:

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') {

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

array PalindromeRadii = [0,...,0]

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)] '''{'''

'''while''' Center-(Radius + 1) Radius >= Radius+10 '''and'''

Center+(Radius + 1) < length(S') '''and'''

'''while''' Center-(Radius+1) >= 0 '''and''' Center+(Radius+1) < length(S') '''and''' S'[Center-(Radius + 1)] = S'[Center+(Radius + 1)] '''{'''

PalindromeRadii[Center] Radius = 2*Radius + 1

'''}'''

// Save the radius of the longest palindrome in the array

PalindromeRadii[Center] = 2*Radius

PalindromeRadii[Center] = 2 * Radius

Center = Center + 1

'''}'''

longest_palindrome_in_S' = max(PalindromeRadii)

longest_palindrome_in_S = (longest_palindrome_in_S' - 1) / 2

'''return''' longest_palindrome_in_S

}