Manacher's algorithm is used to find the longest palindromic substring in a given string in linear time. There are other solutions to find the longest palindromic substring in a given string ranging from O(n2) to O(n log n) but Manacher's algorithm tries to do it in O(n) time.
How does Manacher's algorithm work
Manacher's Algorithm uses the combination of symmetry and center expansion to solve the problem.
- Symmetry- Palindromes are inherently symmetrical around their center. If center is c and string s is a palindrome of length 7 then the sub-string (3 characters) on the right side of c is a mirror image of sub-string (3 characters) on the left side of c. With in a given boundary Manacher’s algorithm tries to look for other potential palindromes using this symmetry in an optimized way which avoids redundancy. Will try to explain this point with the help of few examples afterwards.
- Center Expansion- It is the process of expanding in both directions from a center character, one character at a time on both left and right side and checking if both characters are equal. If yes, then it adds to the palindrome.
Another optimization in Manacher's algorithm is to transform the given string by inserting special characters (like "#") between each character in the String so that string is always odd in length. That way you don't need separate logic for odd length and even length strings.
For the string "1221", the transformed string becomes "#1#2#2#1#". So, from length 4 it transforms to string of length 9. For the string of length n length of the transformed string is (2n+1).
Manacher's algorithm - Java Program
We need to initialize an array LPS to store length of the palindrome around each value of i. Also, variables center and right to center and right boundary of the current longest palindrome.
Transform the string by inserting character ("#") between each character in the String.
Traverse the transformed string and for each i (where 0 <= i < transformedstring.length)
- Calculate the mirror position using 2 * center – i
- Check if (right > i) then set lps[i] = Math.min(lps[mirror], right-i);
This is the optimization in the Manacher’s algorithm to reuse the previous palindrome information from the mirror position. - Compare the characters around i to check if the palindrome can be further expanded.
- If there is an expansion then reposition the center and right to reflect the current palindrome length.
center = i; right = i + lps[i];
import java.util.Arrays;
public class Manacher {
public static void main(String[] args) {
Manacher m = new Manacher();
String s = "pqpypqpypqq";
//String s = "pppqpyp";
//String s = "9121312187";
String str = m.longestPalindrome(s);
System.out.println(str);
}
public String longestPalindrome(String s) {
int n = s.length();
char[] newStr = new char[2*n+1];
int p = 0;
int[] lps = new int[2*n+1];
int maxLength= 0;
int maxCenter = 0;
// modify string to ensure it is always of odd length
for(int i = 0; i < 2*n; i++) {
newStr[i++] = '#';
newStr[i] = s.charAt(p++);
}
newStr[2*n] = '#';
System.out.println("Transformed String is " + Arrays.toString(newStr));
int center=0, right = 0;
for(int i = 0; i < newStr.length; i++) {
int mirror = 2 * center - i;
System.out.println("LPS array " + Arrays.toString(lps));
// this is the optimization in Manacher's algorithm,
// To check with in the right boundary if there is any
// other palindrome by looking into mirror part of it
if(right > i) {
lps[i] = Math.min(lps[mirror], right-i);
}
int r = i + (lps[i]+1);
int l = i - (lps[i]+1);
while(l >= 0 && r < newStr.length && newStr[r]==newStr[l]) {
l--;
r++;
lps[i]++;
}
if(lps[i] >= maxLength) {
maxCenter = i;
maxLength = lps[i];
}
//with comparisons in while loop we have a palindrome
// going beyond right boundary so extend right
if(i + lps[i] > right) {
center = i;
right = i + lps[i];
}
}
// convert char array to string
String st = new String(newStr);
return st.substring(maxCenter - maxLength, maxCenter + maxLength).replace("#", "");
}
}
Output
Transformed String is [#, p, #, q, #, p, #, y, #, p, #, q, #, p, #, y, #, p, #, q, #, q, #] LPS array [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] LPS array [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] LPS array [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] LPS array [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] LPS array [0, 1, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] LPS array [0, 1, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] LPS array [0, 1, 0, 3, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] LPS array [0, 1, 0, 3, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] LPS array [0, 1, 0, 3, 0, 1, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] LPS array [0, 1, 0, 3, 0, 1, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] LPS array [0, 1, 0, 3, 0, 1, 0, 7, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] LPS array [0, 1, 0, 3, 0, 1, 0, 7, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] LPS array [0, 1, 0, 3, 0, 1, 0, 7, 0, 1, 0, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] LPS array [0, 1, 0, 3, 0, 1, 0, 7, 0, 1, 0, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] LPS array [0, 1, 0, 3, 0, 1, 0, 7, 0, 1, 0, 9, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0] LPS array [0, 1, 0, 3, 0, 1, 0, 7, 0, 1, 0, 9, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0] LPS array [0, 1, 0, 3, 0, 1, 0, 7, 0, 1, 0, 9, 0, 1, 0, 5, 0, 0, 0, 0, 0, 0, 0] LPS array [0, 1, 0, 3, 0, 1, 0, 7, 0, 1, 0, 9, 0, 1, 0, 5, 0, 0, 0, 0, 0, 0, 0] LPS array [0, 1, 0, 3, 0, 1, 0, 7, 0, 1, 0, 9, 0, 1, 0, 5, 0, 1, 0, 0, 0, 0, 0] LPS array [0, 1, 0, 3, 0, 1, 0, 7, 0, 1, 0, 9, 0, 1, 0, 5, 0, 1, 0, 0, 0, 0, 0] LPS array [0, 1, 0, 3, 0, 1, 0, 7, 0, 1, 0, 9, 0, 1, 0, 5, 0, 1, 0, 1, 0, 0, 0] LPS array [0, 1, 0, 3, 0, 1, 0, 7, 0, 1, 0, 9, 0, 1, 0, 5, 0, 1, 0, 1, 2, 0, 0] LPS array [0, 1, 0, 3, 0, 1, 0, 7, 0, 1, 0, 9, 0, 1, 0, 5, 0, 1, 0, 1, 2, 1, 0] qpypqpypq
As stated above,
if(right > i) {
lps[i] = Math.min(lps[mirror], right-i);
}
This code is the main optimization with in the Manacher's algorithm to reuse the palindrome information around the mirror position of the current index to reduce the number of comparisons.
To understand it better let's take the example of String as "pqpypqpypqq"
After transforming it the transformed String is
"#p#q#p#y#p#q#p#y#p#q#q#"
And intial LPS array is [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Now let's take the scenario when i = 4, right = 6 and center = 3 so there is a palindrome with center as 3 and stretching till right.
And at that time LPS array would have values as shown here-
LPS array [0, 1, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Since right > i, so we need to check if there is any other palindrome with in the right boundary that can be reused. For that we have to get the mirror position of i which is 2.
As you can see characters at index 1 and 3 don't match and that same info is reflected in LPS[2] which is 0. That means there is no palindrome to reuse and check for palindrome around i (which is 4) has to start from
int r = i + (lps[i]+1) = 5 int l = i - (lps[i]+1) = 3
When i = 5, right = 6 and center = 3, at that time mirror position of i is 1.
As you can see, at mirror position 1 there is a palindrome of length 1 around mirror index and that same info is reflected in LPS[1] which is 1. So, we can safely deduce that index 0..2 will be same as index 4..6 and that information can be used. So, the check for palindrome around i (which is 5) has to start from
int r = i + (lps[i]+1) = 7 int l = i - (lps[i]+1) = 3
If we skip to the scenario when i = 11, right = 14 and center = 7 with mirror position of i as 3.
At that time LPS array will look like-
[0, 1, 0, 3, 0, 1, 0, 7, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
As you can see at mirror position 3 there is a palindrome of length 3 around mirror index and that same info is reflected in LPS[3] which is 3. So, we can safely deduce that index 0..6 will be same as index 8..14 and that information can be used. We never go beyond the right boundary while trying to see what can be reused because we are only sure of the values that are with in the range that is already checked not beyond that.
In this scenario we can start character comparison on the left and right side using the following indices.
int r = i + (lps[i]+1) = 15 int l = i - (lps[i]+1) = 7
Time and space complexity of Manacher's algorithm
There is a pre-processing step to transform the string taking O(n) time.
In the program, with in the for loop, there is an inner while loop too, so it may seem that the time complexity should be O(n2) but the thing is with each matching comparison right also moves one step forward and it is never decreased. That means right also traverse from 0 to n. Therefore, the inner while loop doesn't get executed more than n times.
Then the substring operation to get the final result can also be termed as O(n) operation. Thus, the overall time complexity is O(n), removing any constants.
An array is needed to keep tracks of palindrome lengths around each index. Thus the space complexity of Manacher's algorithm is O(n).
That's all for this topic Manacher's Algorithm to Find The Longest Palindrome - Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!
>>>Return to Java Programs Page
Related Topics
You may also like-
No comments:
Post a Comment