【模板】manacher

原文

我们在原字符串中间添加 # 使得 manacher 可以同时处理奇偶回文

我们对于每一个 i ，若其未超出最大匹配到的范围，则使其按照区间内对称点对称，并按照其对称点的回文长度以及当前 i 到区间右端点取最小值更新当前 i 的回文长度。否则归为 1 。之后朴素算法更新答案，由于中间的那一个字符(包括 #)的对称点是其自身，所以更新后长度要减一。最后如果得到更远的回文范围我们就对范围进行更新。

#include
using namespace std;
char a[11000010],s[22000210]; 
int len;
void change()
{
	s[0]=s[1]='#';
	for(int i=0;i=0&&i+dr[i]maxr) 
		{
			maxr=i+dr[i];
			mid=i;
		}
	}
}
int main()
{
	scanf("%s",a);
	len=strlen(a);
	change();
	manacher();
	for(int i=0;i