manacher

#include 
using namespace std;
const int N = 2e7;
char s[N << 1], ss[N];
int n, ans, p[N << 1];
void manacher(){
	//预处理字符串 
	s[0] = '-', s[1] = '#';
	for (int i = 0; i < n; ++ i){
		s[2 * i + 2] = ss[i];
		s[2 * i + 3] = '#';
	}
	n = 2 * n + 1;
	s[n + 1] = '+'; //计算回文子串的数量时，要记得清空，消除之前的字符对当前答案的影响
	//p[i] 为第 i 个字符为中心的最大回文子串的半径（字符串 s 的）
        //p[i] - 1 为原字符串中第 i 个字符的回文串长度
	int mid = 0, r = 0;
	for (int i = 1; i < n; ++ i){
		if (i < r) p[i] = min(p[(mid << 1) - i], r - i);
		else p[i] = 1;
		while (s[i - p[i]] == s[i + p[i]]) p[i]++;
		if (i + p[i] > r){
			r = i + p[i];
			mid = i;
		}
		ans = max(ans, p[i] - 1);  //求最长回文串长度
	}
	cout << ans << "\n";
}
int main(){
	cin >> ss;
	n = strlen(ss);
	manacher();
	return 0;
}

洛谷模板： https://www.luogu.com.cn/problem/P3805
acwing模板： https://www.acwing.com/problem/content/3190/

洛谷题目：
https://www.luogu.com.cn/problem/P1659 前缀和 + manacher
https://www.luogu.com.cn/problem/P4555 manacher
https://www.luogu.com.cn/problem/P5446 manacher
https://www.luogu.com.cn/problem/P6216 kmp + manacher + 前缀和