好像没发过manacher的板子，反正有现成的
简单介绍一下：
manacher是用来求回文串的算法，它最后可以得到一个数组r[i]，表示以i为中心的最长回文串半径为r[i]。
但是，回文串可能会有abba、abcba两种形式，当长度为偶数时，不好确定中心点。
所以，在字符间加入特殊符号，把它变成这种形式：@a#b#b#a$ 就可以保证长度为奇数了。
首先，预处理把字符串的长度变为奇数。
然后，从1到n求出每一位的r[i]。
设现在i+r[i]最大（也就是回文区间的右端点最靠右）的i为mid，i+r[i]（右端点）为right。
若现在枚举的i>right，直接两端暴力枚举即可；
若现在枚举的i<right，则当前的i被一个大区间包括了（因为mid比i先枚举，一定小于i，而right大于i）。
所以说，既然在这个区间内，那么i和关于mid对称的点j（ (i+j)/2=mid，即j=2mid-i ）的回文区间长度至少是相同的。
但是，这个区间也不能超过大区间的端点right，因为那后面的还没走过，就管不着了。
所以，可以得出r[i] = min(r[2*mid-i],right-i)。
在这个基础上再向外暴力枚举即可。
代码如下
#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #define MogeKo qwq using namespace std; const int maxn = 11000005; int n,p[maxn<<1],ans; char a[maxn],s[maxn<<1]; void change() { s[0] = ‘@‘; s[1] = ‘#‘; for(int i = 0; i < n; i++) { s[i*2+2] = a[i]; s[i*2+3] = ‘#‘; } n = n*2+2; s[n] = ‘$‘; } void manacher() { int mr = 0,mid; for(int i = 1; i <= n; i++) { if(i < mr) p[i] = min(p[mid*2-i],mr-i); else p[i] = 1; while(s[i-p[i]] == s[i+p[i]]) p[i]++; if(i+p[i] > mr) { mr = i+p[i]; mid = i; } } } int main() { scanf("%s",a); n = strlen(a); change(); manacher(); for(int i = 0; i < n; i++) ans = max(ans,p[i]); printf("%d",ans-1); return 0; }
原文：https://www.cnblogs.com/mogeko/p/12452396.html