Longest palindromic substring: Difference between revisions

Revision as of 07:12, 8 May 2023

Revision as of 07:21, 8 May 2023

Line 55:

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}}

Longest_Palindrome(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

Radius = 0

'''while''' Center < length(S') '''{'''

// At the start of the loop, Radius is already set to a lower-bound for the longest radius.

// for the longest //radius. In the first iteration, Radius is 0, but
// it can be higher on later iterations.

// Determine the longest palindrome starting at Center-Radius and
// going to Center+Radius

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

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

Line 82 ⟶ 91:

OldRadius = Radius

Center = Center+1

// Radius' default value will be 0, if we reach the end of the following loop.

// following loop.

Radius = 0

'''while''' Center <= OldCenter + OldRadius '''{'''

// Becausewhile Center lies inside the old palindrome<= andOldCenter every+ characterOldRadius inside{

// a palindrome has a "mirrored" character reflected across its center, we

// Because Center lies inside the old palindrome and every

// can use the data that was precomputed for the Center's mirrored point.

// character //inside a palindrome has a "mirrored" character reflected across its center, we

// reflected across its center, we can use the data that was

// can use the data that was precomputed for the Center's mirrored point.

MirroredCenter = OldCenter - (Center - OldCenter)

MaxMirroredRadius = OldCenter + OldRadius - Center

'''if''' PalindromeRadii[MirroredCenter] < MaxMirroredRadius '''{'''

// the palindrome centered atif PalindromeRadii[MirroredCenter] is entirely contained in the palindrome centered< atMaxMirroredRadius OldCenter{

// So, MirroredCenter and Center have the same sized palindrome

// The palindrome centered at MirroredCenter is entirely

// contained in the palindrome centered at OldCenter So,

// So, MirroredCenter and Center have the same sized palindrome

PalindromeRadii[Center] = PalindromeRadii[MirroredCenter]

Center = Center+1

'''}''' else if PalindromeRadii[MirroredCenter] > MaxMirroredRadius {

'''else if''' PalindromeRadii[MirroredCenter] > MaxMirroredRadius '''{'''

// The palindrome at MirroredCenter extends beyond the palindrome at OldCenter

// palindrome at //OldCenter The palindrome at Center must end at the edge of the OldCenter palindrome

// end at the edge of the OldCenter //palindrome Otherwise, the palindrome at OldCenter would be bigger

// the palindrome at OldCenter would be bigger

PalindromeRadii[Center] = MaxMirroredRadius

Center = Center+1

'''}''' else { // PalindromeRadii[MirroredCenter] = MaxMirroredRadius

'''else {''' // PalindromeRadii[MirroredCenter] = MaxMirroredRadius

// Since the palindrome at MirroredCenter ends exactly at
// the edge of the palindrome centered at OldCenter, the

// the palindrome at Center might be bigger Set Radius to the

// Set Radius to the minimum size of the palindrome at Center so it doesn't
// recheck unnecessarily

Radius = MaxMirroredRadius

'''break''' // exit while loop early

'''}'''

'''}'''

'''}'''

// A palindrome's size is equal to its radius * 2. However, since our variable

// variable Radius considers our bogus characters to the side of the center, the size of

// its corresponding palindrome is actually 2 * (Radius / 2), which means a

// palindrome'scenter, the size is equal toof its corresponding Radiuspalindrome is valueactually in2 PalindromeRadii*

// (Radius / 2), which means a palindrome's size is equal to its

// corresponding Radius value in PalindromeRadii

longest_palindrome_in_S = max(PalindromeRadii)

'''return''' longest_palindrome_in_S

}