Leetcode : LongestPalindromicSubString
Diffculty：Medium
求最长回文子串。
这是一个在面试中比较常出现的算法题。最优解法是Manacher算法，实际上用的是动态规划的思路，首先通过增加间隔符，将结果变为找aba类型的回文串，然后利用已经找到的回文串结果，逐个向后查找更长的回文串。只需遍历一遍字符串即可。
题目
给一个字符串，找出其中最长的回文子串。
注意 aba 和 abba 都属于回文字符串。
目前有两种解法：
1）Manacher算法：时间复杂度O(N)
2）中心点扩散法：时间复杂度O(N^2)
Manacher算法参考思路：https://segmentfault.com/a/1190000003914228
解法
Manacher算法：
/**
* Manacher 算法
* 充分利用回文特性，将字符中间插入 # 将单双回文统一转化为单回文问题
* 然后维护一个数组p，该数组保存以 i 点为中心，最长的回文半径。
* 那么p[i]-1 就是原字符中，以i为中心的回文长度
* 那么问题的结果就是 max(p[i]) - 1
*
* 重点在于计算数组p
*
* 时间复杂度：O(N)
*/
public static String manacher(String str){
char[] t = preprocess(str);
int[] p = new int[t.length]; // p[i] 表示以p为中心的最长的回文半径
int mid = 0; // 已触及的最右边的回文串 在p数组中的 索引 即 p[i] 的 i
int maxRight = 0; // 已触及的最右边的回文串，即 p[i]的值
int length = 0; // 存储p数组中最大的值
int center = 0; // 该最大值的中心index
for(int i=1; i<t.length-1; i++){
int mirror = 2*mid -i; // i相对于mid的对称镜像位置
if(i < maxRight){
// i 在maxRight的左边
// 则p[i] 可以暂时赋值为 镜像位置和maxRight-1 之间的最小值
// 如果p[mirror] 小于maxRight-i 那么 p[i] 肯定是等于 p[mirror]
// 如果p[mirror] 大于maxRight-i 那么 p[i] 至少等于 maxRight-i 由于 maxRight之后还没有比较过，需要从maxRight+1开始关于i对称进行比较。
if(p[mirror] < maxRight-i){ // 注意 这里必须是小于。只有小于边界才能确定 p[i]=p[mirror] 等于只能确定至少是这样
p[i] = p[mirror];
// 已得到p[i] 结果，与length比较
if(p[i] > length){
length = p[i];
center = i;
}
continue;
}else{
p[i] = maxRight-i;
}
}
// p[i] 向两边扩散，相等则值+1。直到找到不等的为止
while(t[i+(1+p[i])] == t[i-(1+p[i])]){
p[i]++;
}
// d得到最终p[i]的值以后
// 如果 maxRight 在 i+p[i] 左边
// 则maxRight=i+p[i] 顺便将回文中点置为i 即 mid=i;
if(i+p[i] > maxRight){
mid = i;
maxRight = i + p[i];
}
// 把当次p[i] 计算结果与 最长结果比较并替换
if(p[i] > length){
length = p[i];
center = i;
}
}
return str.substring((center-1-length)/2, (center-1+length)/2);
}
// 预处理 处理成 $#a#b#c#d#e#@ 的形式
// 头部$ 尾部@ 然后用# 隔开每一个元素
// 由于回文字串会有奇数串和偶数串
// 转为为 #a#b#a# 或者 #a#b#b#a# 以后，长度统一为了奇数个
private static char[] preprocess(String str){
char[] t = new char[str.length()*2 + 3];
t[0] = '$'; //起始边界
t[str.length()*2 + 2] = '@'; //结束边界
for(int i=0; i<str.length(); i++){
t[2*i +1] = '#';
t[2*i +2] = str.charAt(i);
}
t[str.length()*2 + 1] = '#'; //补上最后一个#
return t;
}
中心点扩散法
//回文子串结果
static int lIndex = 0;
static int rIndex = 0;
static int maxLength = 0;
/**
* 中心点扩散法, 通过了leetcode
* @param str
* @return
*/
public static String longestPalindrome(String str){
if(str == null || str.length() <=2){
return str;
}
for(int i=0; i<str.length(); i++){
searchPalind(str, i, i);
searchPalind(str, i, i+1);
}
// 最后仅执行一次substring
return str.substring(lIndex, rIndex);
}
/**
* 从中间向两边找回文字串在 str 中的最大索引范围。
* @param str
* @param low
* @param high
*/
private static void searchPalind(String str, int low, int high){
while(low>=0 && high<str.length()){
if(str.charAt(low) == str.charAt(high)){
if(high-low+1 > maxLength){
lIndex = low;
rIndex = high+1;
maxLength = high - low + 1;
}
}else{
// 如果不等于就退出
return;
}
low--;high++;
}
return;
}
