问题定义
最长回文子串问题：给定一个字符串，求它的最长回文子串长度。
解法1：暴力解法
找到字符串的所有子串，判断每一个子串是否是回文串。
一个子串有该串的起点和终点确定，因此对于长度为N的字符串共有 N2个子串， 这些子串的平均长度为N/2 (判断是否是回文串的时间复杂度O(N)). 因此时间复杂度O(N3)
解法2：改进暴力解法
所有的回文串都是关于某个位置对称。
长度为奇数回文串以最中间字符的位置为对称轴左右对称；
长度为偶数的回文串以中间两个字符之间的空隙为对称轴左右对称。
我们可以遍历字符串中的这些位置, 从每个位置同时向左右扩展，直到两边的字符不同，或达到边界。这类位置共 N + N-1 = 2N-1个，且在每个位置上大约要进行N/4次字符比较，因此算法复杂度O(N2)
解法3：Mancher算法
解法2存在的缺陷：
- 存在很多子串被多次重复访问比较的情况
- 回文串的长度的奇偶性，造成不同的对称轴位置，解法2需要分别处理
步骤1：解决因回文串的长度的奇偶性需要分别处理对称轴的问题
方法：在字符串的开头和末尾，以及每两个字符的中间位置插入唯一标识符#.
这样构造字符串后，字符串的长度始终是奇数。 例如，
aba ==> #a#b#a#
abba ==> #a#b#b#a#
步骤2：解决子串多次重复访问的问题
为了最大程度的利用已经访问过的回文串的信息， Manacher算法巧妙的定义了回文半径: 即，回文串最左或最右位置到对称轴的距离。
回文半径数组RL, RL[i]表示以第 i 个字符为对称轴的回文串的回文半径。例如，
RL[i]值的性质：RL[i]-1 表示 原始字符串中以 第 i 个位置为对称轴 的最长回文串长度。
证明：
在改造过的字符串中，以 第 i 个位置为对称轴的回文串的 最左和最右字符一定是 #.
第i个位置对应的字符，分两种情况，（如图1）:
- 第i个位置对应的字符是 #，则回文串共有奇数个字符，从回文串的最左位置到第i个位置共有，(RL[i]-1)/2 个非#字符， (RL[i] - (RL[i]-1)/2)个#字符， 由于左右关于第 i 个位置对称，因此,该回文串中非#字符共有 (2 * (RL[i]-1)/2) = (RL[i]-1)个非#字符。
- 第i个位置对应的字符是 非#字符，则回文串共有偶数个字符，从回文串的最左位置到第i个位置共有，RL[i]/2-1 个非#字符 (减1是为了不计算第 i 个位置的字符)， (RL[i] - RL[i]/2+1)个#字符， 由于左右关于第 i 个位置对称，因此,该回文串中非#字符共有 (2 * (RL[i]/2-1)) + 1 = (RL[i] - 1)个非#字符 （最后的+1，是将第 i 个位置也算上）。
步骤3：如何利用RL数组，减少重复访问字符串
为了尽可能的减少重复访问字符串的次数，引入变量 MaxRigth 表示 在从左到右，已经访问过的回文串中，回文串所能触及到字符串的最右位置，即该回文串的中心为pos，则其关系如下图2所示：
idx在4和12之间的所有字符都关于pos位置对称！
由于pos是已经访问过的位置，则 当前访问到的位置 i 只能位于pos的右边，且有两种情况：
1）当前访问的位置 i 在MaxRight的左边，如图3所示
从图中可以看出，以位置 i 为中心的回文串必然与以pos为中心的回文串存在一部分的重合。
现在我们想找出以位置 i 为中心的回文字符，为了减少重复访问字符，我们希望可以知道以位置 i 为中心的左右两边哪些字符已经是对称的。
我们知道，以pos为中心的左右两边对称，位置 i 在pos的右边，那么在pos的左边必然存在和 位置 i 对称的位置（假设我们记该对称的位置为 j）。如图3中的idx=6 。
由于位置 j 已经访问过，我们知道以位置 j 为中心的回文串回文半径, 此处分两种情况讨论：
- 以位置 j 为中心的回文串在 位置pos和位置Maxright的对称位置之间，如图4所示.
如图所示，由于以位置 j 为对称轴的回文串的回文半径已知，根据对称性，我们知道位置 i 的左右邻居对称，因此可以从左右邻居开始寻找以位置 i 为对称抽的回文串，这样便减少了对字符的重复访问。
- 以位置 j 为中心的回文串不在 位置pos和Maxright的对称位置之间，如图5所示.
此时我们只能确定红色线条之间字符关于位置 i 对称，但这也减少了重复访问字符的次数。此时，只需要从左红线的左端，右红线的右端开始遍历字符、判断对称，寻找最长回文字符。
2）当前访问的位置 i 在 MaxRight的右边，如图6。
此时，说明以位置 i 为对称轴的回文串的左右两侧的对称信息，无法从历史信息中推导出来，我们不得不从位置 i 的左右邻居开始判断是否相同，指定遇到不同的字符或达到边界为止。
步骤4：如何更新RL数组, MaxRight变量，位置pos
if(i < MaxRight){
// RL[i] 初始值
RL[i] = min(RL[pos - (i - pos], MaxRight-i)
}else {
// RL[i] 初始值
RL[i] = 1;
}
以位置 i 为对称轴 从对称轴的左右RL[i]距离处，同时向左右开始访问字符，并同时更新RL[i]
MaxRight = RL[i]+i-1 > MaxRight ? RL[i]+i-1 : MaxRight
pos = RL[i]+i-1 > MaxRight ? i : pos;
算法实现
public int findLongestPalindromicSubstring(String s){
// 填充字符, 假设字符#在s中没有出现过
String cs = "#";
for(int i=0; i<s.length(); ++i){
cs += s.charAt(i);
cs += "#";
}
// 保存最长的回文字符串的长度
int maxlen = 0;
int[] RL = new int[cs.length()];
int maxRight=0, pos=0;
for(int i=0; i<cs.length(); ++i){
// 根据 i 位于maxRight的左边还是右边更新RL[i]
if(i < maxRight){
// i 在maxRight左边的情况
RL[i] = Math.min(RL[2*pos-1], maxRight-i);
}else{
// i 在maxRight右边的情况
RL[i]=1;
}
// 边界判断, 回文判断
while(i+RL[i]<cs.length() && i-RL[i] >=0 && cs.charAt(i+RL[i])==cs.charAt(i-RL[i])){
++RL[i];
}
if(RL[i]+i-1 > maxRight){
maxRight = RL[i] + i -1;
pos = i;
}
// 更新最长回文字符串的长度
maxlen = maxlen > RL[i] ? RL[i] : maxlen;
}
// 利用RL的性质
return maxlen-1;
}
复杂度分析
空间复杂度：插入分隔符形成新串，占用了线性的空间大小；RL数组也占用线性大小的空间，因此空间复杂度是线性的。
时间复杂度：尽管代码里面有两层循环，通过平摊分析，我们可以得出，Manacher的时间复杂度是线性的。由于内层的循环只对尚未匹配的部分进行，因此对于每一个字符而言，只会进行一次，因此时间复杂度是O(n)。
注：文本主要参考了文献[1]，并在理解的基础上，做了些许更改。
