它可以做什么？

~~马拉车~~manachaer算法可以在O(n)的时间内求出字符串中的最长回文串长度

它是怎么实现的？

考虑f[i]表示字符串中以第i个字符为中心的最长回文串长度，求f[i]时，若已求出的回文串中末端最靠右者f[maxmid]的末端位置的位置maxright>i，表明i与位置 2maxmid-i关于maxmid对称，则f[i]可以通过f[2maxmid-i]更新，否则f[i]设置为1

需要注意的是，由于maxright右侧的字符情况未知，所以f[i]最大只能更新到2*(maxright-i)+1

之后，暴力延长f[i]判断即可

这样就求出了所有以i为中心的最长回文串的长度

可是……这样求出的回文串长度是奇数的，偶数长度怎么办？

我们可以通过在字符之间插入一些~~奇奇怪怪的~~无关字符来使得原字符串长度为奇数，这样就可以方便地求出所有f[i]，只需在输出答案时处理一下即可

真棒，那代码呢

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#include <queue>
#define maxlen 11000010
using namespace std;

char in[maxlen],str[2*maxlen];
int len;
int ans,f[2*maxlen];

int main()
{
	register int i;
	scanf("%s",in+1);
	len=strlen(in+1);
	str[1]='#',str[0]='^';//注意此处,需要在串前使用一个更特殊的字符防止过度延展
	for(i=1;i<=len;++i)
	{
		str[i*2]=in[i];
		str[i*2+1]='#';
	}
	
	f[1]=1;
	len=strlen(str+1);
	int nowmid=1,nowright=1;
	for(i=1;i<=len;++i)
	{
		if(i<nowright)
			f[i]=min(f[2*nowmid-i],2*(nowright-i)+1);
		else
			f[i]=1;
		int x=f[i]/2;
		while(str[i-x-1]==str[i+x+1] && i-x-1 && i+x+1<=len)
		{
			++x;
			f[i]+=2;
		}
		if(i+x>nowright)
		{
			nowmid=i;
			nowright=i+x;
		}
		ans=max(ans,f[i]);
	}
	printf("%d",ans/2);
	return 0;
}
//by:liz

上面的代码可以直接运行于Luogu 3805