【题解manacher-1】最长回文子串的长度
同 leet 5. 最长回文子串
描述
给定一个字符串str, 返回str中最长回文子串的长度
[举例]
str=“123”。其中的最长回文子串“1”或者“2”或者“3”，所以返回1。
str=“abc1234321ab”。其中的最长回文子串“1234321”，所以返回7。
[要求]
如果str的长度为N，解决原问题的时间复杂度都达到O(N).
输入描述：
输入为一个字符串str
输出描述：
输出一个整数表示最长回文子串的长度
示例1
输入：
123
输出：
1
示例2
输入：
abc1234321ab
输出：
7
备注：
设N表示输入字符串的长度保证输入字符中只含有小写字母及数字1⩽N⩽5∗1051⩽N⩽5∗105
简单直观实用中心扩展方法，时间复杂度是O(n*n)。但manacher方法可以把时间复杂度降低到O(n)，很多地方把manacher描述成复杂算法，事实上，只需要理解几个关键步骤就可以弄清楚manacher算法。
步骤一：问题转换，找bcbaaaa的最长回文子串，转成寻找字符串#b#c#b#a#a#a#a#的最长回文子串，
对于奇数串bcb转成计算#b#c#b#，对于偶数串aaaa转成#a#a#a#a#，不影响计算结果，避免了偶数串没有中心字符不容易扩展的情景，实现代码：
public static char[] transfer(char[] s1){
char[] s2=new char[2*s1.length+1];
for(int i=0,j=0;i<s2.length;i++){
s2[i]= (i&1)==0 ?'#': s1[j++];
}
return s2;
}
步骤二：使用转换字符串计算最长回文子串。先看算法：
public String longestPalindrome(String str) {
char[] s=transfer(str.toCharArray());
int n=s.length;
int[] p=new int[n];
int C=-1,R=-1,L=-1,max=0;
int left=-1,right=-1;
for(int i=0;i<s.length;i++){
p[i]=R>i?Math.min(p[2*C-i],R-i):1;
while(i-p[i]>=0 && i+p[i]<s.length && s[i+p[i]]==s[i-p[i]] ) p[i]++;
if(i+p[i]>R){
R=i+p[i];
C=i;
}
if(max<p[i]){
max=p[i];
left=i+1-p[i];
right=i-1+p[i];
}
}
StringBuilder sb=new StringBuilder();
for(int i=left;i<=right;i++){
if(s[i]!='#') sb.append(s[i]);
}
return sb.toString();
}
几个关键变量：
int[] p 数组值 p[i] 表示转换字符串#b#c#b#a#a#a#a#的以位置i为中心向左右扩展始终保持回文串的最大半径（注意是半径不是回文串的长度）。很明显最长回文子串出现的时候p[i]是最大的，p[i]默认值是1。根据p[i]=>最长回文子串。
int R=-1，C=-1，表示循环变量i所在位置为中心的时候，最长回文子串能够延伸到右边出现的最远的位置，C是出现最远位置时候的中心位置i。所以任何时候；R=Math.max(i+p[i])。定义R和C的目的是为了帮助计算p[i],p[i]又帮助计算最长回文子串。
问题一：R和C如何帮助计算p[i]，理解公式p[i]=p[2*C-i]
答案是依赖回文串左右对称的特性，依据对称特性，理想情况下C左边出现位置字符的p[i]应该和其对称右边出现字符的p[i]相等以上面i=3为例，此时C=3，R=6. 后面i=4和i=5,i=6 的i+p[i] 分别是4+1=5，5+2=7，6+1=7 最远都没有超过i=3的R=3+p[3]=7。
所以i=4，i=5, i=6 的p[i]可以根据 以C为中心的回文串#b#c#b#已经计算过的p[2]和p[1],p[0] 获取。其中p[2]和p[4]以C=3为中心对称，p[1]和p[5]以C=3为中心对称,p[0]和p[6]以C=3为中心对称=》p[2*C-i]与p[i]以位置C为中心左右对称，而且应该相等。
问题二：如何理解：p[i]=R>i?Math.min(p[2*C-i],R-i):1; //备注，此处是manacher能够优化时间复杂度的重要步骤。
为何理想情况下p[i]=p[2*C-i]？ p[i]在R以内的最大值是R-i，所以p[i]在R能协助的范围以内的值=Math.min(p[2*C-i],R-i)。超出了R，p[i]默认=1，因为R之前没有任何可以参照使用的的p[i]。 举例如下：
问题三，是否p[i]=R>i?Math.min(p[2*C-i],R-i):1 到此就万事大吉了呢？为何后面还有
while(i-p[i]>=0 && i+p[i]<s.length && s[i+p[i]]==s[i-p[i]] ) p[i]++;
p[i]=R>i?Math.min(p[2*C-i],R-i):1 只是用已经有的经验算出了p[i]此时至少应该是这么多，R后面的字符还没有探索过，所以需要继续在p[i]基础之上继续向两边扩展，如果两边仍然能扩展而且字符相同则p[i]++.
后续需要根据计算好的p[i]迭代R和C。R始终=max(i+p[i])
if(i+p[i]>R){
R=i+p[i];
C=i;
}
在计算好的p[i] 的基础之上，当出现最大p[i]的值的时候，是最长回文子串出现的时候，所以用left，right记录此时左边界和右边界。p[i]的left到i的长度是p[i]此时i-left+1=p[i]所以left=i+1-p[i]. 同理 right=i-1+p[i]
if(max<p[i]){
max=p[i];
left=i+1-p[i];
right=i-1+p[i];
}
总结，理解manacher算法需要，
1)字符串转换manacher字符串，
2)i迭代每个转换字符的位置，
3)p[i]记录每个i位置为中心的最长回文串半径，用已经有的结果，在此基础之上继续两边扩展
4) R和C分别记录右边出现更大位置i+p[i] 的时候的R和中心位置i,
5）出现更大p[i[的时候记录字符串起始和结束位置。
总之还是比较简单的。
上面题目要求最长回文子串的长度,代码如下：
public static int maxLcpsLength(String str) {
char[] s = transfer(str.toCharArray());
int[] p = new int[s.length];
int R = -1,C = -1;
int max = Integer.MIN_VALUE;
for (int i = 0; i < s.length; i++) {
p[i] = R > i ? Math.min(p[2 * C - i], R - i) : 1;
while (i + p[i] < s.length && i - p[i] >=0 && s[i + p[i]] == s[i - p[i]]) p[i]++;
if (i + p[i] > R) {
R = i + p[i];
C = i;
}
max = Math.max(max, p[i]);
}
return max - 1;
}
同系列题目：
投递淘天集团等公司10个岗位