部分转载自洛谷manacher题解，图是自己魔改的
【用途】
- 求一个字符串中有多少个回文子串。
【算法过程】
- 预处理
由于回文串分为偶回文串和奇回文串，奇偶判断起来比较麻烦。
因此我们可以在字符串的首、尾以及各个字符之间添加一些“神奇”字符（不妨使用\(|\)）。
但是要注意字符串的首添加的字符要另外区别于各个字符之间的字符,这是为了在扩展时及时终止，防止越界
不难发现，修改后的字符串都变成了奇字符串。
以下Manacher算法的所有处理都是基于修改后的字符串。
例如：
st="a b a a b a"，那么s="& | a | b | a | a | b | a | "
- Manacher算法的主体
-
定义数组p[i]表示以字符i为回文中心的最长回文串的半径。
-
p[i]-1就是字符串中最长回文串的长度（因为要去除|）
举个例子：
对于对称中心为\(|\) 的串
c | a | a | b，明显成立
& | a | a | b |明显成立
对于对称中心为字符的串串：
& | A | B | A | C | ，发现也很明显成立
接下来可以讨论代码主体：
-
定义\(mx\)和\(mid\)，表示目前找到的回文串的右端的最右是mx，中心是mid。
-
如上图所示，\(mid\)是\(mx'\) ~ \(mx\)的回文中心，因此在黄色范围内以\(i\)的对称点\(j\)为回文中心的字符串=以\(i\)为回文中心的字符串，因此\(p[i]\)可以是\(p[j]\)。
-
但是由于超过\(mx\)的部分（即右紫色斜线部分）不能保证必定等于左紫色斜线的部分，所以\(p[i]\)不能超过\(i\) ~ \(mx\)的长度。
-
因此 \(p[i]=min(mx-i,p[mid*2-i])\)
接下来，我们就要暴力统计右侧 “不能保证” 的部分，即最右黑边的右侧是否满足回文性质（具体看代码）
最后更新一下mx即可。
【时空复杂度】 -
因为势能分析可得，\(p[i]\)的移动都不会超过\(n\)次，所以可以保证正确性
-
因为每次\(ma\)和\(p[i]\)取\(max\)，所以保证递增，保证复杂度
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define M 40000005
char s[M],st[M];
int p[M];
int gets(){
int len=strlen(st);
int j=2;
s[0]='-';s[1]='|';
for(int i=0;i<len;i++){
s[j++]=st[i];
s[j++]='|';
}s[j]='&';
return j;
}int manacher(){
int len=gets(),mid=1,mx=1,ans=-1;
for(int i=1;i<len;i++){
if(i<mx) p[i]=min(mx-i,p[mid*2-i]);
else p[i]=1;
while(s[i-p[i]]==s[i+p[i]]) p[i]++;
if(mx<i+p[i]){
mid=i;
mx=i+p[i];
}//cout<<p[i]<<" "<<i<<endl;
ans=max(ans,p[i]-1);
}return ans;
}
int main(){
scanf("%s",st);
printf("%d\n",manacher());
return 0;
}