//
// Created by Administrator on 2021/8/11.
//
#ifndef C__TEST02_MANACHER_HPP
#define C__TEST02_MANACHER_HPP
#include <iostream>
#include <vector>
using namespace std;
class Manacher {
public:
static vector<char> manacherString(string s){
vector<char> res(2*s.size() + 1);
int index = 0;
for(int i = 0; i<res.size(); ++i){
res[i] = (i&1) == 0? '#' : s[index++];
}
return res;
}
static int manacherAlgrithm(string s){
if(s.empty()){
return -1;
}
//加#
vector<char> str = manacherString(s);
//记录每个位置的回文半径
vector<int> arr(str.size());
//中心和半径
int C = -1;
int R = -1;
int maxValue = INT_MIN;
for(int i = 0; i < str.size(); ++i){
//arr[i]初始值
//如果当前i小于回文半径, 就是R - i和对称点回文半径最小值,否则是1
arr[i] = R > i ? min(R - i, arr[2*C - i]) : 1;
/* 不管什么情况都继续两边扩,如果不相等马上break
* 例如arr[i] = 1
* 将会从+1-1开始往外扩
* 如果arr[i] 大于1, 也就是周围那么大范围已经是回文了
* 所以从 i加减arr[i]往外扩
* */
while(i-arr[i] > -1 && i+arr[i] < str.size()){
if(str[i - arr[i]] == str[i + arr[i]]){
arr[i]++;
}else{
break;
}
}
if(arr[i] > R){
R = i + arr[i];
C = i;
}
maxValue = max(maxValue, arr[i]);
}
return maxValue - 1;
}
};
#endif //C__TEST02_MANACHER_HPP