#include<bits/stdc++.h>
using namespace std;
struct Manacher {
struct Char {
char ch;
Char(){}
Char(char ch) : ch(ch) {}
Char &operator = (const char &r) {
ch = r;
return *this;
}
bool operator == (const Char &r) const {
if(ch == '#' && r.ch == '#') return true;
/* 此处写字符等于的逻辑 */
}
};
int len;
string s;
vector<Char> str;
vector<int> p;
Manacher(string &s) : s(s) {
str.push_back('$');
str.push_back('#');
for(int i = 0; i < (int) s.size(); i++) {
str.push_back(s[i]);
str.push_back('#');
}
str.push_back('~');
len = str.size() - 1;
for(int i = 1, mid = 0, mx = 0; i <= len; i++) {
if(i < mx) p[i] = min(p[2 * mid - i], mx - i);
else if(str[i] == str[i]) {
p[i] = 1;
}
else p[i] = 0;
for(; str[i - p[i]] == str[i + p[i]]; ++p[i]) {
/* 此处写求半径数组p的时候需要顺带处理的信息 */
}
if(i + p[i] > mx) {
mx = i + p[i];
mid = i;
}
}
}
};