首先我们先来看一个题：给定一个字符串str，返回str中最长回文子串的长度。比如str = “123”，其中的最长回文子串为"1"、“2”、“3”，所以返回1。又比如str = “abc1234321ab”，其中的最长回文子串为"1234321"，所以返回7。
面对字符串"a131b"，我们寻找字符串中回文子串的最直观的想法也许是在遍历字符串的过程中，以当前字符为中心，向两边“扩”来对比两边的字符是否相等，然后记录回文子串长度。比如当前遍历到的字符为a，只有右边有字符，所以回文子串"a"的长度为1；当遍历到的字符为1时，左右两边的字符分别为’a’和’3’不相等，所以回文子串"1"的长度为1；当遍历到的字符为3时，左右两边的字符都为’1’，记录下长度，然后继续向两边比较，此时‘a’和’b’不相等，所以回文子串"131"的长度为3。。。
但是我们会发现这种方法并不适用于偶数长度的字符串，比如字符串"y1221p"就无法像上面的方法一样求得最大回文子串"1221"的长度为4。
解决的办法是在字符串的两边和字符之间添加字符，比如添加字符"#"，当然也可以其他任意一种字符，读者可以自行尝试。对于字符串"1221"添加完字符后就变为"#1#2#2#1#"，此时我们上面的寻找最长回文子串长度的方法可以运用于偶数字符串和奇数字符串中，不过添加完字符后的字符串所统计出来的回文子串长度是没添加字符前的字符串的两倍。
上面的方法的时间复杂度为O(n^2)，下面我们使用Manacher算法来达到O(N)时间复杂度的实现。
首先我们需要明白三个概念：
- 回文半径数组pArr：回文半径数组就是用于存储回文子串的半径长度的数组。比如字符串"#c#a#b#a#c#"，其回文半径数组就为[1，2，1，2，1，6，1，2，1，2，1]。
- 最右回文半径指针pR：该指针每次都会指向当前或之前回文子串最右边字符的下一个字符。如果当前回文子串的最右字符超出了之前回文子串的pR的范围，即当前回文子串的最右字符比pR所指向的字符更右，那么pR就更新为当前回文子串最右边字符的下一个字符，否则就不变。下面我们以字符串"#a#b#a#"为例，来看一下pR指针的移动过程。观察下图，cur表示遍历到的当前字符。
后面的过程中pR不再移动，cur一直往右移动，直到等于字符串长度停下。
- 回文子串中心指针index：回文子串中心指针是随着pR变化的，也就是pR改变时，index也会变化。观察上图，当cur指向第一个字符’#‘时，pR发生改变并指向了’a’，此时回文中心指针index指向当前回文子串"#“的中心位置，即cur指向的位置。当cur指向第二个字符’a’时，pR发生改变并指向了字符’b’，此时回文中心指针index指向当前回文子串”#a#"的中心位置，同样也是cur指向的位置，后面的同理。
在理解了上面的三个概念之后，我们再来看在遍历的过程中当前指针i可能会面临如下两种情况：
第一种情况：观察下图，[L…pR-1]是回文子串，index为回文子串的中心指针。此时当前指针i在pR的右边时（包括pR），我们就像普通解法一样，从i位置字符开始向左右两边开始“扩”，即以当前字符为中心寻找其最大的回文子串半径长度。
第二种情况是i在pR指针左边，如下图所示：
此时可以又可以分为下面三种子情况：
情况1：观察下图，i’是i关于index对称的位置，且i’已经有其对应的回文子串半径值pArr[i’]。假如以i’为中心的回文子串（下图左边蓝色区域）包含于大回文子串[L…pR-1]中，那么我们可以直接得出i的回文半径即为i’的回文半径值。
这个很好证明，因为[L…index-1]与[index + 1…pR – 1]关于index对称，那么上图中蓝色与绿色区域的字符串也关于index对称，又因为蓝色区域是回文子串，那么自然绿色区域也是回文子串，他们长度相等，所以回文半径也相等。
情况2：观察下图，i’是i关于index对称的位置。假如以i’为中心的回文子串（下图左边蓝色区域）的左边界超过了最大回文子串[L…pR-1]的左边界，那么我们可以直接得出i的回文半径即为i到pR的距离的长度pR – i。
我们同样可以证明这个结论是正确的。观察上图，[L…pR-1]是回文子串，X和Y关于i’对称并相等，Y与X’关于index对称并相等，X与Y’关于index对称并相等，那么就有X=Y=X’≠Y’，所以以i为中心的回文子串的即为上图中的绿色区域，其半径等于i到pR的距离pR – i。
情况3：观察下图，i’是i关于index对称的位置。此时以i’为中心的回文子串（下图左边蓝色区域）的左边界刚好与最大回文子串[L…pR-1]的左边界重合，那么此时i为中心的回文半径至少等于i’的回文半径。
当然，i为中心的回文半径可能更大，比如上图中，X如果等于Y那么以i为中心的回文半径长度+1。由于无法向上面两种情况一样直接得出以i为中心的回文半径长度，那么需要X和Y位置开始向两边"扩"以寻找更大的回文子串半径长度。
综合上述分析，其具体代码实现如下所示：
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
65
66
67
2
3 //该方法将形如"abccba"的字符串转为形如"#a#b#c#c#b#a#"
4 public static char[] manacherString(String str) {
5 char[] chs = str.toCharArray();
6 char[] charArr = new char[2 * str.length() + 1];
7 for (int i = 0, j = 0; i < charArr.length; i++) {
8 charArr[i] = (i & 1) == 0 ? '#' : chs[j++];
9 }
10 return charArr;
11 }
12
13 public static int maxLcpsLength(String str) {
14 if (str == null || str.length() == 0)
15 return 0;
16 // 获取源字符数组
17 char[] charArr = manacherString(str);
18 // 定义一个回文半径长数组pArr
19 int[] pArr = new int[charArr.length];
20 // 定义最右回文指针，每次都指向当前回文子串的最右字符的下一个字符
21 int pR = -1;
22 // 定义当前回文子串的回文中心节点坐标
23 int index = -1;
24 // 记录最大回文半径值
25 int max = Integer.MIN_VALUE;
26
27 for (int i = 0; i < charArr.length; i++) {
28 // 先根据i是否在pR左边来给pArr[i]一个初始值，然后再根据实际情况，
29 // 即是否需要从i往外扩来增大pArr[i]的值
30 /*
31 * 1. 如果i在pR的右边，那么先给pArr[i]赋值1,即半径大小至少等于自己本身的长度
32 * 2. 如果i在pR的左边，那么i关于index的对称点i'的半径值为pArr[2 * index - i]，
33 * 2.1 如果i'的左半径超过以index为中心的回文子串的左边界，那么其pArr[i]至少为pArr[2 * index - i]。
34 * 2.2 如果i'的左半径没有超过以index为中心的回文子串的左边界，那么其pArr[i]为pR - i。
35 * 2.3 如果i'的左半径与以index为中心的回文子串的左边界重合，那么其pArr[i]为pArr[2 * index - i]。
36 */
37 pArr[i] = i < pR ? Math.min(pArr[2 * index - i], pR - i) : 1;
38 // 下面两个循环条件分别表示在从i向两边扩时的最右边界和最左边界
39 while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {
40 //比较当前左右半径的外面的字符是否相等，相等则半径加1
41 if (charArr[i - pArr[i]] == charArr[i + pArr[i]]) {//1和2.1会执行
42 pArr[i]++;
43 } else {
44 break;//2.2和2.3的情况会执行
45 }
46 }
47 // 更改最右回文指针，每次都指向当前i为中心回文子串的最右字符的下一个字符
48 // 更改当前回文子串的回文中心节点坐标
49 if (i + pArr[i] > pR) {
50 pR = i + pArr[i];
51 index = i;
52 }
53
54 //更新最大回文子串长度
55 max = Math.max(max, pArr[i]);
56 }
57
58 return max - 1;
59 }
60
61 // for test
62 public static void main(String[] args) {
63 System.out.println(maxLcpsLength("olocbadebcolo"));
64 }
65}
66
67
