Manacher’s Algorithm is used to solve the problem of longest Palindromic Substring problem. Compared with brute force solution (which time complexity is O(N^3), and space complexity is O(N^3)), Manacher’s Algorithm is much better. (Time complexity is O(N), space complexity is O(N)). This post is going to illustrate this amazing algorithm.

preprocess the String

When we are solving this problem, we may need to classify different situation: 1. String.length() is odd 2. String.length() is even
We can preprocess the origin string to make it easier.
The solution is:

1
2

bob -> !#b#o#b#
noon -> !#n#o#o#n#

The reason for the first element “!” is to avoid crossing the border.For example, when matching #b#o#b#, we will match to index -1 and index 7. And it

Then the main idea of this algorithm is:
we need to create another array to store the number of palindromic substring. For example:

1
2

!#n#o#o#n#          <- s
1121252121		   <- Len

In this example, I call that array “p”. And the max(Len) -1 should be the length of the longest Palindromic Substring. When our question becomes -> how to calculate this array Len.

Main idea

i <= rightMax:

First Condition

In this condition, Len[i] = Len[j]. Because the rightest index of palindromic string at index i is less than the rightMax.

Second Condition

In this condition, We know that Len[i] <= Len[j], so when we are calculating Len[i], it will be quicker if we can use the known information of Len[j]. What we need to do is to compare the expanded string to check whether we can expand this palindromic Substring.

i > rightMax

In this condition, we know i is not in the range of the palindromic string at index middlePoint. So we know nothing of index i. What we need to do is compare the expanded string and check. Also, update the middlePoint and rightMax after the caculation.

Java code of this algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

	public String longestPalindrome(String s) {
//		initialize the array
		String t = "!#";
		for(char s1 : s.toCharArray()){
			t += (s1+"#");
		}
		int[] p = new int[t.length()];
		int id = 0, mx = 0, resLen = 0, resCenter = 0;
		for(int i = 1; i < t.length(); i++){
			p[i] = mx > i?Math.min(mx-i, p[2*id-i]):1;
			while(i+p[i] < t.length()){
				if(t.charAt(i+p[i]) == t.charAt(i-p[i])){
					p[i]++;
				}
				else{
					break;
				}
			}
			if(mx < i + p[i]){
				id = i;
				mx = i + p[i];
			}
			if(resLen < p[i]){
				resLen = p[i];
				resCenter = i;
			}	
		}
		return s.substring((resCenter-resLen)/2, (resCenter-resLen)/2 + (resLen-1));
    }

If you have any questions, please leave a comment below.

Comments: