manacher
<pre><code>#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;
}</code></pre>