manacher算法
计算回文长度时，一般用 manacher 算法，回文串长度可以是奇数也可以是偶数，mamacher 算法在存的时候克服了这个问题。
字符串：abba，ababa
不难看出两个字符串都是回文串，第二个回文串直接找到回文中心就可以了判了，但是第一个就有点棘手。
manacher 算法将所有相邻的字符之间补上一个字符，直接找对称中心就行了。
如果一个回文串长度为 $n$。
- 假如 $n$ 是奇数，那么有 $n-1$ 个间隔，增加了偶数个字符。
- 假如 $n$ 是偶数，同样有 $n-1$ 个间隔，增加了奇数个字符。
显然，偶数加奇数是奇数，所以一定有对称中心。
对称
保证有了对称中心，就可以通过枚举对称中心两边比对来找回文串即可。
但是 manacher 的精髓不仅于此。
我们将对称中心的回文长度存到 h_w[i] 中，原字符串是 a_a。
while(a_a[i+h_w[i]]==a_a[i-h_w[i]])h_w[i]++;//两边辐射 我们通过枚举两边可以知道回文串的长度，但是在记录的过程中我们也可以用到它对称的特性，
举个例子：qwertrewqwertrewq
这个回文串有两个回文子串：qwertrewq，如果我们单纯的考暴力枚举的话，找到所有的回文串要将所有的字枚举为回文中心，并枚举回文长度，来计算。
但是当我们枚举回文中心时，枚举完第一个回文串（qwertrewq）和第二个回文串时（qwertrewqwertrewq）。根据对称这一特性，我们其实已经可以断言第三个回文串（qwertrewq）的存在了。
所以当我们枚举到第三个回文串的对称中心时可以直接从第一个回文串那里获得基本信息，再向两边遍历查找（有可能在大回文串外的字符和串里的字符仍然回文）。
例子：qwerewqwerewqwe
我们可以发现，我们可以从第一个 qwerewq 和 qwerewqwerewq 断言第二个 qwerewq 的存在，并在第一个串中获得基本信息：回文长度，但是并没有结束，因为它的极限是 ewqwerewqwe，所以还要继续判断。
manacher的优化程度
在上面的例子中我们发现 manacher 的优化就是一个获得信息。
对于大数据用这种优化和暴力相比复杂度应该不大吧？还不如暴力记得方便？
我们上面举的例子都是“相对友好的”，看看那下面的两个例子。
例子：qwqwqwqwqwq 和 qqqqqq
我们把它们延长几万倍，暴力和 manacher 的差距就对比出来了。
if(i<=r)h_w[i]=min(h_w[m_i*2-i],r-i+1);//对称找最大回文 因为信息要传大回文串里的所以要注意不能超过大回文串的回文中心。
例子：ewqwerewqwerewq
所以第二个 qwerewq 只能保留第一个 qwerewq的信息，而非 ewqwerewqwe 的，所以这里用一个 min，来规范边界。
代码
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<vector>
#include<bitset>
#include<map>
using namespace std;
const int o_o=3e7+10;
string a;
char a_a[o_o];
int l_a,m_a;
int h_w[o_o];
void r_r(){
char c=getchar();
a_a[l_a++]='@';a_a[l_a++]='|';
while(c<'a'||c>'z')c=getchar();
while(c<='z'&&c>='a'){
a_a[l_a++]=c;
a_a[l_a++]='|';
c=getchar();
}
}
int main(){
r_r();
for(int i=1,m_i=0,r=0;i<=l_a;i++){
if(i<=r)h_w[i]=min(h_w[m_i*2-i],r-i+1);//对称找最大回文
while(a_a[i+h_w[i]]==a_a[i-h_w[i]])h_w[i]++;//两边辐射
if(h_w[i]+i>r)r=h_w[i]+i-1,m_i=i;//快速跳边界
m_a=max(m_a,h_w[i]);//记录最长
}
cout<<m_a-1<<endl;
return 0;
}
