Manacher algorithm - Longest Palindromic Substring

O(N) time and O(N) space

题目

给定一个字符串str，返回str中的最长回文子串的长度。
str=“123”。其中的最长回文子串“1”或者“2”或者“3”，所以返回1。
str=“abc1234321ab”。其中的最长回文子串“1234321”，所以返回7。

思路

  • 解决字符串奇偶问题，在源字符串每个字符添加一个字符，包括首尾，这个字符是任意的
1
2
s: a b c 1 2 3 4 3 2 1 a b
t:#a#b#c#1#2#3#4#3#2#1#a#b#
  • 设定p[]表示的是以该字符为中心的最大回文半径
1
2
3
s:a b c 1 2 3 4 3 2 1 a b
t:#a#b#c#1#2#3#4#3#2#1#a#b#
p:0101010101010701010101010

从p可以看出最大回文长度为7,因多了字符，所以不用除2

  • 求p[]的过程

设置index和r
index:以index位置为中心
r:以index位置为中心，最大的回文半径所在的坐标位置
这两个值是随时更新的

三种情况：

  1. 当i的对称点p[i_mirro]在回文半径r-index内部时，p[i]=p[i_mirro]
  2. 当i的对称点p[i_mirro]在回文半径r-index位置上，p[i]=p[i_mirro],然后再继续遍历找p[i]
  3. 当i的对称点p[i_mirro]在回文半径r-index外部时，直接遍历找p[i]

see more: Longest Palindromic Substring

代码

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
//对字符串添加
public char [] changeToManacher(String s){
	char [] c = s.toCharArray();
	char [] res = new char[c.length * 2 + 1];
	for(int i = 0;i <res.length; i++){
		if(i % 2 == 0){
			res[i] = '#';
		}else{
			res[i] = c[i/2];
		}
	}
	return res;
}
public String Manacher(String s){
	char [] t = changeToManacher(s);
	int [] p = new int[t.length];
	int index = 0, r = 0;
	//第一个和最后一个的p都是0
	for (int i = 1; i < t.length -1 ; i++){
		int i_mirro = 2*index - i;//i的关于index的对称点 = index + i - index
		
		
		if(r < i){
			//当i在r之外,关于自己对称是p是0
			p[i] = 0;
		}else{
			//i在r内部，或在r的位置
			//在r的位置时，p为0
			p[i] = Math.min(p[i_mirro], r-i);
		}
		
		//对于在外部或者在r位置的状况，只能遍历两侧是否为回文
		while(i + p[i] +1 < t.length - 1 && i - p[i] -1 > -1){
			if(t[i + p[i] +1] == t[i - p[i] -1]){
				p[i]++;
			}else{
				break;
			}
			
		}
		
		//更新index和r
		//r是最长回文半径所在位置的坐标
		if(i + p[i] > r){
			r = i + p[i];
			index = i;
		}
		
	}
	
	//找到最长的回文长度
	int maxP = 0;
	int center = 0;
	for (int i = 1; i < t.length - 1; i++){
		if(p[i] > maxP){
			maxP = p[i];
			center = i;
		}
	}
	
	return s.substring((center - maxP)/2, maxP);
	
}