package com.jiucaiyuan.net.question;
/**
* Manacher算法
* 解决问题：字符串str中，最长回文子串的长度如何求解？
* 如何做到时间复杂度O(N)完成？
*
* @Author jiucaiyuan 2022/5/2 13:29
* @mail services@jiucaiyuan.net
*/
public class Manacher {
/**
* <pre>
* <b>求输入字符s的最大回文子串（非子序列）</b>
* <b>Manacher算法</b>（最长回文子串）
* 【算法中概念】：
* R 最右回文边界 （代码中表示回文边界的下一个位置，为了写代码方便）
* C 最右回文边界R对应的回文中心位置
* L R关于C的对称点
* pArr 回文半径数组pArr[]，pArr[i]表示以i位置为中心找最大回文，得到的回文半径长度赋值给pArr[i]
* 【不同情况处理】
* 1）当前点，没有在最右回文边界R里（在R之外）
* 暴力破
* 2）当前点，相对C的对称点i`的回文区域在L和R内部（R相对C点的对称点是L）
* 这时候i的回文半径和i`的回文半径一样
* 3）当前点，相对C的对称点i`的回文区域，一部分跑到L的外面
* 这时候i的回文半径是i到R距离（R-i）
* 4）当前点，相对C的对称点i`的回文区域，左侧正好压在L上
* 这时候i的回文半径从R开始，继续向右验证（i到R内不需要验证）
* </pre>
*
* @param s
* @return
*/
public static int maxLengthPalindromeSubString(String s) {
if (s == null || s.length() == 0) {
return 0;
}
char[] str = manacherString(s); //12321 ——> #1#2#3#2#1#
int[] pArr = new int[str.length]; //回文半径数组，每个字符的回文半径组成的数组 经过下面for代码后，回文半径数组被填充了
int C = -1; //最右回文边界R对应的回文中心位置
int R = -1; //最右回文边界再往右一个位置，最右的有效区是 R-1 位置
int max = Integer.MIN_VALUE; //扩出来的最大值
for (int i = 0; i != str.length; i++) { //每个位置都求回文半径
//如果i在R外，不用验的区域是1
//如果i在R内，Math.min(pArr[2 * C - i], R - i) 2 * C - i是i`的位置，R-i
//所以i至少的回文半径区域赋值给pArr[i]
//i<R 表示i在R内 各种情况不用验的区域都汇聚到此
pArr[i] = i < R ? Math.min(pArr[2 * C - i], R - i) : 1;
//不用验（是否回文的区域、加速）的区域确定后，并没有超过边界，继续进行尝试
while (i + pArr[i] < str.length && i - pArr[i] > -1) {
//不用验的区域确定后，再尝试往两边验证下是否相同，如果相同，回文半径++
if (str[i + pArr[i]] == str[i - pArr[i]]) {
pArr[i]++;
} else {
break;
}
}
//如果扩完发现R可以变大，则记录最大回文半径R及对应的中点C
if (i + pArr[i] > R) {
R = i + pArr[i];
C = i;
}
//记录以每个字符为中心往外扩找最大回文时的最长回文长度
max = Math.max(max, pArr[i]);
}
//max是加特殊字符后的回文半径，原始串的回文长度正好等于加特殊字符后的回文半径-1
return max - 1;
}
/**
* 把输入的字符串加工成加入#字符的新字符数组
* 如：输入"12345"，返回['#','1','#','2','#','3','#','4','#','5','#']
* @param str 原始字符串
* @return 原始字符串空隙加入特殊字符#后对应的字符数组
*/
public static char[] manacherString(String str) {
char[] charArr = str.toCharArray();
char[] res = new char[str.length() * 2 + 1];
int index = 0;
for (int i = 0; i != res.length; i++) {
res[i] = (i & 1) == 0 ? '#' : charArr[index++];
}
return res;
}
public static void main(String[] args) {
String str = "abc1234321ab";
System.out.println(str+"最长回文子串长度="+maxLengthPalindromeSubString(str));
}
}