Manacher

参考资料

• Manacher - OI Wiki

实现

299 Bcpp

int p[N<<1];
int manacher(string s)
{
	int n=s.size();
	string t="@#";
	for(int i=0;i<n;i++)
	{
		t+=s[i];
		t+='#';
	}
	t+='&';
	s=t;
	n=n<<1|1;
	for(int i=1,l=0,r=0;i<=n;i++)
	{
		p[i]=i<=r?min(p[2*l-i],r-i+1):1;
		while(s[i-p[i]]==s[i+p[i]])p[i]++;
		if(i+p[i]-1>r)r=i+p[i]-1,l=i;
	}
	return n;
}

例题

洛谷 P3805 【模板】manacher

给出一个只由小写英文字符组成的字符串 $S$，求 $S$ 中最长回文串的长度。

洛谷 P4555 [国家集训队] 最长双回文串

给定长度为 $n$ 的字符串 $S$，求 $S$ 的最长双回文子串 $T$，即可将 $T$ 分为两部分 $X, Y$（$|X|,|Y|\ge1$）且 $X$ 和 $Y$ 都是回文串。