manacher

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int maxn = 1e5+6;
string str;
int p[maxn];
void init(string &str){
    int len = str.size();
    str.insert(0, "$");
    for(int i = len+1; i > 0; i--){
        str.insert(i, "#");
    }
    return;
}
int Manacher(string str){
    init(str);
    int max_len = -1;
    int center;
    int max_size = 0;
    for(int i = 1; i < str.size(); i++){
        if(i < max_size){
            p[i] = min(p[2*center - i], max_size-i);
        }
        else    p[i] = 1;
        while(str[i+p[i]] == str[i-p[i]])    p[i]++;
        if(i + p[i] > max_size){
            center = i;
            max_size = i + p[i];
        }
        max_len = max(max_len, p[i] - 1);
    }
    return max_len;
}