Manacher（回文子串）

O（n）求一个字符串中的最大回文子串

#include<bits/stdc++.h>
using namespace std;
const int N=100000+10;
int n,num,res,p[N<<2];
string a,b;
char c[N<<2];
void init()
{
	c[num++]='$';
	c[num++]='#';
	for(int i=0;i<a.size();i++)
	{
		c[num++]=a[i];
		c[num++]='#';
	}
}
void Manacher()
{
	int id;
	int mx=0;
	for(int i=1;i<=num;i++)
	{
		if(i<mx)	p[i]=min(p[2*id-i],mx-i);
		else	p[i]=1;
		while(c[i-p[i]]==c[i+p[i]])	p[i]++;
		if(mx<i+p[i])	id=i,mx=i+p[i];
		res=max(res,p[i]-1);
	}
}
int main()
{
	cin>>n>>a;
	init();
	Manacher();
	cout<<res<<endl;
	return 0;
}