题解 P3805 【【模板】manacher算法】

考虑判断回文的方法 1.暴力 最朴素的暴力 举出该字符串的所有子串，判断其是否回文，时间复杂度是$O(n^3)$的 2.改进第一种，仍然是暴力 所有的回文串都是对称的。长度为奇数回文串以最中间字符的位置为对称轴左右对称，而长度为偶数的回文串的对称轴在中间两个字符之间的空隙。可以遍历这些对称轴，在每个对称轴上同时向左和向右扩展，直到左右两边的字符不同或者到达边界。 时间复杂度$O(n^2)$ 3.manacher算法 首先我们可以先查看第二种方法有哪些缺点 1）回文串长度的奇偶性造成了对称轴的位置可能在某字符上，也可能在两个字符之间的空隙处，第二种方法要对两种情况分别处理 那么manacher对此的优化是这样的 在每两个字符中间插入另一个字符，如'#'。 也就是说，原来的字符串是这样的  现在的字符串是这样的（为了不越界以及方便，a[0]设置为‘#’）  那么这个缺点解决了 2）会出现很多子串被重复多次访问，时间效率大幅降低。 这里比较难理解 用一个辅助数组hw表示每个点能够扩展出的回文长度 我们从s[1]遍历到s[strlen(s)]，循环变量为i 我们先设置一个辅助变量maxright，表示已经触及到的最右边的字符 另外还要设置一个辅助变量mid，表示包含maxright的回文串的对称轴所在的位置 也就是这样：  当i在maxright左边且在mid右边时： 设i关于mid的对称点为j，显然hw[i]一定不会小于hw[j]。（对称） 我们没必要保存j，j可以通过计算得出，为： $(mid<<1)-i$,可以尝试自己算 那么我们就设置hw[i]=hw[j]然后继续尝试扩展，这样就可以较快地求出hw[i]，然后更新maxright和mid 当i在maxright右边时，我们无法得知关于hw[i]的信息，只好从1开始遍历，然后更新maxright和mid 这样就是这个算法的全部了，如果认真读了是不会太难的，实在不行可以百度。 而该算法的时间复杂度和空间复杂度都是线性的 小结：manacher就是利用回文对称的性质，来简化求以一个字符为对称轴的最大的回文长度。别看这简化不大，当数据很大时，这样求的速度会快很多。 下面是代码： ```cpp #include<iostream> #include<cmath> #include<cstring> #define maxn 51000100 using namespace std; int n,hw[maxn],ans; char a[maxn],s[maxn<<1]; void manacher() { int maxright=0,mid; for(int i=1;i<n;i++) { if(i<maxright) hw[i]=min(hw[(mid<<1)-i],hw[mid]+mid-i); else hw[i]=1; for(;s[i+hw[i]]==s[i-hw[i]];++hw[i]); if(hw[i]+i>maxright) { maxright=hw[i]+i; mid=i; } } } 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]=0; } int main() { scanf("%s",a); n=strlen(a); change(); manacher(); ans=1; for(int i=0;i<n;i++) ans=max(ans,hw[i]); printf("%d",ans-1); return 0; } ``` 如果哪里有问题可以在评论提出，谢谢orz