Talk:Longest palindromic substring

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

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

   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

   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")