Manacher
(string/manacher.hpp)

#pragma once
#include<string>
#include<vector>

/**
 * @brief Manacher
 */

std::vector<int> manacher(std::string S){
    int i = 0, j = 0;
    std::string s;
    for(int i=0;i<(int)S.size();i++){
        if(i)s+='$';
        s+=S[i];
    }
    int n=s.size();
    std::vector<int>res(n,0);
    while (i<n) {
        while(i-j>=0&&i+j<n&&s[i-j]==s[i+j])++j;
        res[i]=j;
        int k=1;
        while (i-k >= 0 && k+res[i-k]<j)res[i+k]=res[i-k],++k;
        i+=k;j-=k;
    }
    for(int i=0;i<n;++i){
        if(i%2)res[i]=res[i]/2;
        else res[i]=(res[i]+1)/2;
    }
    return res;
}

#line 2 "string/manacher.hpp"
#include<string>
#include<vector>

/**
 * @brief Manacher
 */

std::vector<int> manacher(std::string S){
    int i = 0, j = 0;
    std::string s;
    for(int i=0;i<(int)S.size();i++){
        if(i)s+='$';
        s+=S[i];
    }
    int n=s.size();
    std::vector<int>res(n,0);
    while (i<n) {
        while(i-j>=0&&i+j<n&&s[i-j]==s[i+j])++j;
        res[i]=j;
        int k=1;
        while (i-k >= 0 && k+res[i-k]<j)res[i+k]=res[i-k],++k;
        i+=k;j-=k;
    }
    for(int i=0;i<n;++i){
        if(i%2)res[i]=res[i]/2;
        else res[i]=(res[i]+1)/2;
    }
    return res;
}