题解 P3805 【【模板】manacher算法】
codesonic
·
·
题解
考虑判断回文的方法
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可以通过计算得出，为：
那么我们就设置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