Manacher总结

# Manacher总结 ### 【用途】 - 求一个字符串中有多少个回文**子串**。 ### 【算法过程】 #### 1. 预处理 - 由于回文串分为偶回文串和奇回文串，奇偶判断起来比较麻烦，因此我们可以在字符串的首、尾以及各个字符之间添加一些“神奇”字符（不妨使用$），但是要注意字符串的首添加的字符**必须**区别于各个字符之间的字符。 - 不难发现，修改后的字符串都变成了奇字符串。 - **以下Manacher算法的所有处理都是基于修改后的字符串**。 #### 2. Manacher算法的主体 - 定义数组p[i]表示以字符i为回文中心的最长回文串的半径，不难发现，p[i]-1就是字符串中最长回文串的长度（因为要去除$）。 - 定义mx和mid，表示目前找到的回文串的右端的最右是mx，中心是mid。 -  - 如上图所示，id是j~mx的回文中心，因此以i的对称点为回文中心的字符串=以i为回文中心的字符串，因此p[i]可以是p[j]。但是由于超过mx的部分（即右红边部分）**不能保证**必定等于左红边的部分，所以p[i]不能超过i~mx的长度。因此 ```cpp p[i]=min(mx-i,p[mid*2-i]) ``` - 接下来，我们就要**暴力**统计右侧 “不能保证” 的部分，即最右黑边的右侧是否满足回文性质（具体看代码）。 - 最后更新一下mx即可。 ### 【时空复杂度】 - Manacher算法的时间复杂度为$O(n)$（这里就不作证明了），因此是解决回文问题的利器。 ### 【参考程序】 ```cpp #include<cstdio> #include<cstring> #define min(a,b) (a<b?a:b) #define max(a,b) (a>b?a:b) char s[32000005],st[32000005]; int p[32000005]; int change() { 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=change(),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]; } ans=max(ans,p[i]-1); } return ans; } int main() { scanf("%s",st); printf("%d",Manacher()); } ```