$manacher$算法,这个被$OIer$戏称为马拉车的算法,作为字符串入门算法,非常值得$OIer$学习,并且学会其核心思想--不断利用之前以求的值来更新之后待求的值。掌握好它,我们就可以开启$OI$字符串算法的大门。
$manacher$算法是用于求最长回文子串长度的算法。
什么回文串?顾名思义,回文串就是一个字符串顺序读和倒序读都一样。
举个栗子:$aba$ $aaaaaa$ $IOI$
首先,我们来看到问题:给定一个字符串,求其最长回文子串长度。
$1$.我们来看一看最暴力的解法:枚举所有子串,再分别判断该串是否是回文串。时间复杂度$O(n^3)$。暴力不愧是暴力,这时间复杂度直接上天
$2$.既然暴力不行,那我们稍微优化一下。我们可以枚举每一个点作为对称点(就是该回文子串的对称中心),再暴力扫描求出最长回文子串长度。时间复杂度$O(n^2)$。
$3$.改进后还是有点慢,我们可不可以再快一点?这是,我们今天的主角--manacher算法就闪亮登场了。
我们可以沿着$2$的思路,枚举对称点,并令$p[i]$为该对称点所能延伸的最长回文半径(从对称点到该回文子串的左端点或右端点(包含端点和对称点))。
这时,我们遇到了第一个问题--如果是偶回文串,那我们该怎么办? 我们可以在所有字符之间插入一个无关字符,让偶串变成奇串。 举个栗子:aba->@#a#b#a#! (前后两个端点插入不同符号防越界) abba->@#a#b#b#a#! 这样,我们就可以愉快的枚举对称点了。
之后,我们可以得到一个显然才怪的结论--回文串长度==$p[i]-1$。
为了防止我们看的云里雾里,还是补充一个解释比较好:
以abba为例,处理后变成@#a#b#b#a#! 那么最中间的#号的$p[i]$值为$5$,$5-1=4$,从数值上看,它们是相等的。
那有没有什么证明呢?当然要有,不然怎么用这个算法。
新串相当于在原串的基础上$\times 2+1$,我们取它的回文半径就可以抵消掉$\times 2$的效果,再$-1$就可以得到真正的回文串长度。
说了这么多,提升效率的呢?
我们定义$mx$表示当前找到的最长回文子串的最右端点的下标,$id$表示$mx$的对称中心。用$i$表示当前要匹配的节点。
利用回文串的性质,我们可以得到$i$关于$id$对称的点$j=(id<<1)-i$。
显然,$p[i]=p[j]$,且$p[i]$不可以再向两边扩展。
显然,$p[i]=p[j]$,且$p[i]$可以再向两边扩展。
此时$p[i]=mx-i$,且$p[i]$不可以再向两边扩展。
因为如果可以扩展,则$cd$,又因为$ab$且$bc$,所以$ad$,那么$mx$就可以再拓展一位,产生矛盾,舍去。
直接$p[i]=1$,之后再判断是否可以拓展。(因为之前推出的$p[i]$值无法更新当前要求的值)
好了,直接上核心代码
for(R int i=1;i<len;++i) {//len是新数组长度 if(i<mx) p[i]=min(p[(id<<1)-i],mx-i);//同1 else p[i]=1;//同2 while(str[i+p[i]]==str[i-p[i]]) ++p[i];//判断是否可以再向两边拓展 if(p[i]+i>mx) {mx=i+p[i];id=i;}//更新 ans=max(ans,p[i]-1);//更新答案 }
参考资料:
Chrety大佬的blog
老规矩,练手题
1.板子(题解)(我的代码)
2.求前$k$长的所有回文子串长度的乘积(题解)(我的代码)
3.最长双回文串(题解)(我的代码)