Manacher's Algorithm is used for finding sub-palindromes in a given string in linear time. More formally, the problem statement is as follows: Given a string s with length n. Find all the pairs (i,j) such that substring s[i…j] is a palindrome. String t is a palindrome when ( is a reversed string for ).
t=trev
trev
t
Algorithm
Simple approach
A straightforward solution can be iterating through each character of the given string and treating it as a center of a palindrome, i.e. looking at neighboring characters and increasing positions by as long as it's possible, comparing a pair of corresponding characters each time. To avoid the overflow and passing left and right borders, we can add terminal characters to indicate those borders.
The implementation of the trivial algorithm is:
Terminal characters $ and ^ were used to avoid dealing with ends of the string separately.
Manacher's algorithm for odd length string
Let dodd[i] denote the odd-length palindromes centered at i. Let (l,r) be the borders of the rightmost found (sub-)palindrome (i. e. the current rightmost (sub-)palindrome is s[l+1]s[l+2]…s[r−1]). Initially, l=0,r=1, which is an empty string.
Next, we want to calculate dodd[i], so:
If i is outside the current sub-palindrome, i. e. i≥r, we can use the simple approach described above.
If i≤r, let's find the "mirror" position of i in the sub-palindrome (l,r), i.e. we'll get the position j=l+(r−i), and check the value of
dodd[j]. Because j is the position symmetrical to i with respect to (l+r)/2, we can almost always assign dodd[i]=dodd[j]. Illustration of this (palindrome around
j is actually "copied" into the palindrome around
i):
…
A tricky case can be, when the "inner" palindrome reaches the borders of the "outer" one, i. e.
j−dodd[j]≤l (or, which is the same,
i+dodd[j]≥r). Because the symmetry outside the "outer" palindrome is not guaranteed, just assigning
dodd[i]=dodd[j] will be incorrect: we do not have enough data to state that the palindrome in the position
i has the same length.
To handle such situations correctly, we should restrict the length of our palindrome for now, i. e. have dodd[i]=r−i, . After this we'll run the simple approach described above. which will try to increase
dodd[i] while it's possible.
Illustration of this case (the palindrome with center
j is restricted to fit the "outer" palindrome):
…palindromesl+1…sj…palindromesi−(r−i)+1…palindrometry moving here……………
It is shown in the illustration that though the palindrome with center
j could be larger and go outside the "outer" palindrome, but with
i as the center we can use only the part that entirely fits into the "outer" palindrome. But the answer for the position
i (
dodd[i]) can be much bigger than this part, so next we'll run our trivial algorithm that will try to grow it outside our "outer" palindrome, i. e. to the region "try moving here". As a reminder, to work correctly we should update the values (l,r) after calculating each dodd[i].
Implementation for odd length Manacher's algorithm:
Manacher's Algorithm for General Case
While we could use the above approach and modify it to consider two characters as centers of an even-length string, it is possible to reduce the whole problem to the case when we only deal with the palindromes of odd length. To do this, we can put an additional # character between each letter in the string and also in the beginning and the end of the string. This would still maintain the properties of existing palindromes and make a string odd-length:
Here, d[2i]=2deven[i]+1 and d[2i+1]=2dodd[i] where d denotes the Manacher array for odd-length palindromes in #-joined string, while dodd and deven correspond to the arrays defined above in the initial string.
The algorithm with the string adjustment can be implemented as follows: