Talk:Longest palindromic substring
![]() | This article was nominated for deletion on 20 November 2011 (UTC). The result of the discussion was keep. |
![]() | This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||
|
Entire article has been copied from PEGWiki - unsure of what to do here but it looks to me to be written in a far more complex form than we'd expect here on Wikipedia... Nikthestoned 17:21, 31 October 2011 (UTC)
I agree with Nik above. I found the original explanation ... opaque. I bought Manacher's paper from the ACM and rewrote this page. I also wrote some python code to make sure what I wrote was correct. The code is below. Mdnahas (talk) 00:10, 16 March 2021 (UTC)
Manacher's original code translated to Python
[edit]This code actually doesn't try to find the longest palindrome! It tries to find the shortest even-length palindrome that starts at the beginning of the string. If one is found, the return value is the other end of the palindrome, plus 1. If none is found, 0 is returned.
The original code was written in FORTRAN. FORTRAN uses arrays where the first index is 1, instead of 0. This is why the array indexing below contains "minus 1" everywhere.
The original code used "goto". I changed it to "while True" and "break". It required inserting the new variable "JumpToL1".
I deleted all the original's comments, since those might belong to the copyright holder. Thus, all comments below are my own.
"BP" is the beginning pointer, "MDP" is a middle pointer, and "ENP" is the end pointer. With an even-length palindrome, there are actually two characters in the middle and "MDP" is the index of the first one. The original function was called "PAL" and, in FORTRAN, the name of the function is also the name of the value returned by the function. This is why the result is called "PAL" below.
def manacher(D): N = len(D) M = [0]*(N-1) # Allocate list of N-1 elements initialized to 0. ENP = 1 PAL = 0 # This is the result of the function. while True: # This serves as L1 in the original. ENP = ENP + 1 if ENP == N + 1: return (PAL, M) MDP = ENP-1 BP = ENP-1 COUNT = 0 while True: # This serves as L2 in the original. while D[ENP-1] == D[BP-1]: COUNT = COUNT + 1 ENP = ENP + 1 BP = BP - 1 if BP == 0: PAL = ENP return (PAL, M) if ENP == N + 1: return (PAL, M) M[MDP-1] = COUNT JumpToL1 = True for F in range(1, COUNT + 1): # 1 to COUNT, inclusive if M[MDP - F - 1] != COUNT - F: M[MDP + F - 1] = min(COUNT - F, M[MDP - F - 1]) else: MDP = MDP + F COUNT = COUNT - F BP = MDP - COUNT JumpToL1 = False # Jump to L2 break if JumpToL1: break
Slow algorithm in Python
[edit]def find_longest_palindrome_with_odd_length_SLOW(S): KnownRadii = [] Center = 0 while Center < len(S): # Center is an index in S # KnownRadii[x] for x < Center holds the maximal radius of a palindrome for each index x. assert len(KnownRadii) == Center Radius = 0 while Center - (Radius+1) >= 0 and Center + (Radius+1) < len(S) and S[Center - (Radius+1)] == S[Center + (Radius+1)]: Radius += 1 # After the above loop, Radius now holds the maximal radius for the palindrome at index Center KnownRadii.append(Radius) # at index Center Center += 1 return (max(KnownRadii), KnownRadii.index(max(KnownRadii)), KnownRadii)
Manacher's algorithm in Python
[edit]def find_longest_palindrome_with_odd_length(S): KnownRadii = [] Center = 0 Radius = 0 while Center < len(S): # Center is an index in S # Radius is a lower bound for the radius of the palindrome at index Center # KnownRadii[x] for x < Center holds the maximal radius of a palindrome for each index x. assert Center + Radius < len(S) assert len(KnownRadii) == Center while Center - (Radius+1) >= 0 and Center + (Radius+1) < len(S) and S[Center - (Radius+1)] == S[Center + (Radius+1)]: Radius += 1 # After the above loop, Radius now holds the maximal radius for the palindrome at index Center KnownRadii.append(Radius) # at index Center # Update KnownRadii for indexes greater than Center OldCenter = Center OldRadius = Radius Center += 1 Radius = 0 # default value if we reach the end of this loop while Center <= OldCenter + OldRadius: MirroredCenter = OldCenter - (Center - OldCenter) MaxMirroredRadius = OldCenter + OldRadius - Center if KnownRadii[MirroredCenter] < MaxMirroredRadius: KnownRadii.append(KnownRadii[MirroredCenter]) # at index Center Center += 1 elif KnownRadii[MirroredCenter] > MaxMirroredRadius: KnownRadii.append(MaxMirroredRadius) # at index Center Center += 1 else: Radius = MaxMirroredRadius break return (max(KnownRadii), KnownRadii.index(max(KnownRadii)), KnownRadii) a = find_longest_palindrome_with_odd_length_SLOW("aaaaa") print(str(a) + " should be 2,2") a = find_longest_palindrome_with_odd_length_SLOW("abacd") print(str(a) + " should be 1,1")