Palindromes are one of the most beautiful strings in the world but finding the longest palindromic substring is one of the most computationally daunting task. In this post I am going to talk about the Manacher’s Algorithm which achieves this in linear time.
Note : In all the pseudo codes, 0-based indexing is used and the indentations are used to differentiate between block of codes.
Given a string P, find the longest palindromic substring.
Try 1 :
Loosely speaking, we can generate all the substring and check each of these substrings whether they are a palindrome or not. To be more concrete, we run an outer loop which iterates over each and every position of the string P, and for each position we run an inside loop, which generates each substring with that position as the starting point. For each of the generated we run a kind of two pointer method to check if that substring is a palindrome or not.
Pseudo Code :
checkPalindrome(S) for i=0 upto S.Length, j=S.Length-1 to 0 if S[i]!=S[j] return false return true maxLength=0 maxPalindrome=null for i=0 upto P.Length for j=i+1 upto P.Length if checkPalindrome(P[i...j]) and P[i...j].Length>maxLength maxLength=P[i...j].Length maxPalindrome=P[i...j]
Time Complexity : O(|P|3)
Space Complexity : O(1)
One other way in which we can tackle this problem is by observing that each palindrome has a center along which the string becomes symmetric.
For Example :
- S=”radar” has a center at ‘d’
- T=”aayushhsuyaa” has centres at both the ‘h’s.
Using this fact, we can construct a solution to exploiting this fact. More concretely, we will, for each point check whether an odd-length palindrome has a center at that point and compare its length or if an even-length palindrome has a center in the neighbourhood.
Pseudo Code :
maxLength=0 maxPalindrome=null for i=0 upto P.Length // Checking for Odd-Length Palindromes low=i-1 high=i+1 while low>=0 and high<P.Length and P[low]==P[high] if P[low...high].Length>maxLength maxLength=P[low...high].Length maxPalindrome=P[low...high] low-- high++ // Checking for Even-Length Palindromes low=i-1 high=i while low>=0 and high<P.Length and P[low]==P[high] if P[low...high].Length>maxLength maxLength=P[low...high].Length maxPalindrome=P[low...high] low-- high++
Time Complexity : O(|P|2)
Space Complexity: O(1)
Can we do better?
The answer to this lies in Manacher’s Algorithm.
Manacher‘s Algorithm is the most efficient program to find out the longest palindrome in a string. It uses a lot of clever insights to convert the previous quadratic algorithm to a linear algorithm.
Each palindrome has a centre of symmetry.
As shown before, each palindrome has a centre of symmetry about which if we expand we can get the palindrome.
Example: S=”ABABA” has a centre at 3rd position.
Using this subtle fact as a backbone, the algorithm uses an auxiliary string which consists of special character (or more a character which is not present in the string) between each of the letter and having two mutually different characters other than the special character to mark the starting and ending of the string.
Example: For string S given above, the auxililary string, T, will look like $#A#B#A#B#A#@.
Using this string as the starting point solves the dilemma of having two centres for even-length palindromes as for an even-length palindrome, the special character serves as the centre.
Palindromes are symmetric about the centre uptill the boundary.
If we look carefully, right part looks just like the left part of the palindrome. Hence there exists a mirror counterpart for each position of the palinidrome.
Example: Let us take the string S=”ABABA”
However this may seem more than tempting to assume that len(palindrome(right))=len(palindrome(left)).
But the one thing that we are missing right now, is that we are ignoring anything before and after the palindromic substring “ABABA”.
If we consider the string S=”ABABAB”.
So we can actually observe that len(palindrome(right))>=len(palindrome(left)).
Now let us consider another string S=”BABABA”.
So we can observe that len(palindrome(right))>=R-right’s index
Combining the two observations, we get:
If len(palindrome(left)) goes beyond L
If len(palindrome(left)) is within L
Hence len(palindrome(right))>=min(len(palindrome(left)), R-right’s index)
In Manacher's algorithm, for every index element, we expand beyond the minimum length that we get from the above established fact to find the actual length of the palindrome.
Note : The auxiliary string that is constructed should have different starting and ending special characters.
Example : T="@#A#B#A#B#A#@" is a wrong auxiliary string as the end characters are also involved in the largest palindromic substring.
A= C=0, R=0 for i=1 upto T.Length mirr=2*C-i if i<R A[i]=min(R-i,A[mirr]) while(T[i+(1+A[i])]==T[i-(1+A[i])]) A[i]++ if i+A[i]>R C=i R=1+A[i]
Time Complexity : O(|P|)
Space Complexity : O(|P|)
Manacher's Algorithm is one of the most beautiful algorithm, which effectively finds the largest palindromic substring. Although there are not many practical applications of Manacher's Algorithm apart from being used in some compression procedures, it gives a different viewpoint towards strings and in particular palindromes.