Content deleted Content added
→Manacher's algorithm: I put some of the explanation of the algorithm as comments in the code so that it is clearer why it is working. Tags: Mobile edit Mobile web edit |
|||
Line 53:
'''while''' Center < length(S') '''{'''
// At the start of the loop, Radius is already set to a lower-bound 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
Line 79:
MaxMirroredRadius = OldCenter + OldRadius - Center
'''if''' PalindromeRadii[MirroredCenter] < MaxMirroredRadius '''{'''
// the palindrome centered at MirroredCenter is entirely contained in the palindrome centered at OldCenter
// So, MirroredCenter and Center have the same sized palindrome
PalindromeRadii[Center] = PalindromeRadii[MirroredCenter]
Center = Center+1
'''}'''
'''else if''' PalindromeRadii[MirroredCenter] > MaxMirroredRadius '''{'''
// The palindrome at MirroredCenter is bigger than the palindrome at OldCenter
// The palindrome at Center must end at the edge of the OldCenter palindrome
// Otherwise, the palindrome at OldCenter would be bigger
PalindromeRadii[Center] = MaxMirroredRadius
Center = Center+1
'''}'''
'''else {''' // PalindromeRadii[MirroredCenter] = MaxMirroredRadius
// Since the palindrome at MirroredCenter ends exactly at the edge of the palindrome centered at OldCenter,
// the palindrome at Center might be bigger
// Set Radius to the minimum size of the palindrome centered at Center so it doesn't recheck unnecessarily
Radius = MaxMirroredRadius
'''break''' // exit while loop early
'''}'''
| |||