浅谈manacher算法
manacher算法是我在网上无意中找到的,主要是用来求某个字符串的最长回文子串.
不过网上的版本还不太成熟,我就修改了下.
不要被manacher这个名字吓倒了,其实manacher算法很简单,也很容易理解,程序短,时间复杂度为O(n).
求最长回文子串这个问题,我听说有个分治+拓展kmp的算法,不过我估计后缀数组也可以.
但杀鸡岂能用牛刀?
现在进入正题:
首先,在字符串s中,用rad[i]表示第i个字符的回文半径,即rad[i]尽可能大,且满足:
s[i-rad[i],i-1]=s[i+1,i+rad[i]]
很明显,求出了所有的rad,就求出了所有的长度为奇数的回文子串.
至于偶数的怎么求,最后再讲.
假设现在求出了rad[1..i-1],现在要求后面的rad值,并且通过前面的操作,得知了当前字符i的rad值至少为j.现在通过试图扩大j来扫描,求出了rad[i].再假设现在有个指针k,从1循环到rad[i],试图通过某些手段来求出[i+1,i+rad[i]]的rad值.
根据定义,黑色的部分是一个回文子串,两段红色的区间全等.
因为之前已经求出了rad[i-k],所以直接用它.有3种情况:
①rad[i]-k<rad[i-k]
如图,rad[i-k]的范围为青色.因为黑色的部分是回文的,且青色的部分超过了黑色的部分,所以rad[i+k]肯定至少为rad[i]-k,即橙色的部分.那橙色以外的部分就不是了吗?这是肯定的.因为如果橙色以外的部分也是回文的,那么根据青色和红色部分的关系,可以证明黑色部分再往外延伸一点也是一个回文子串,这肯定不可能,因此rad[i+k]=rad[i]-k.为了方便下文,这里的rad[i+k]=rad[i]-k=min(rad[i]-k,rad[i-k]).
②rad[i]-k>rad[i-k]
如图,rad[i-k]的范围为青色.因为黑色的部分是回文的,且青色的部分在黑色的部分里面,根据定义,很容易得出:rad[i+k]=rad[i-k].为了方便下文,这里的rad[i+k]=rad[i-k]=min(rad[i]-k,rad[i-k]).
根据上面两种情况,可以得出结论:当rad[i]-k!=rad[i-k]的时候,rad[i+k]=min(rad[i]-k,rad[i-k]).
注意:当rad[i]-k==rad[i-k]的时候,就不同了,这是第三种情况:
如图,通过和第一种情况对比之后会发现,因为青色的部分没有超出黑色的部分,所以即使橙色的部分全等,也无法像第一种情况一样引出矛盾,因此橙色的部分是有可能全等的,但是,根据已知的信息,我们不知道橙色的部分是多长,因此就把i指针移到i+k的位置,j=rad[i-k](因为它的rad值至少为rad[i-k]),等下次循环的时候再做了.
整个算法就这样.
至于时间复杂度为什么是O(n),我已经证明了,但很难说清楚.所以自己体会吧.
上文还留有一个问题,就是这样只能算出奇数长度的回文子串,偶数的就不行.怎么办呢?有一种直接但比较笨的方法,就是做两遍(因为两个程序是差不多的,只是rad值的意义和一些下标变了而已).但是写两个差不多的程序是很痛苦的,而且容易错.所以一种比较好的方法就是在原来的串中每两个字符之间加入一个特殊字符,再做.如:aabbaca,把它变成a#a#b#b#a#c#a,这样的话,无论原来的回文子串长度是偶数还是奇数,现在都变成奇数了.
hdu3068 最长回文
求最长回文的长度
第一次做Manacher，尽管是个模板题，还是要看标程
标称中有几个困惑的地方，我来记录一下
if(red[k]+k>i)red[i]=min(red[2*k-i],red[k]+k-i);
当时觉得这句好难，其实也不过是上面提到过的，看图
这个， red[k]+k>i就是上文中第1,2种情况的条件，也就是i存在于以k为中心的回文串内
min函数中的两个元素为什么是这两个？？有什么用？？
这便是上图中对两种情况的讨论，x是i关于k对称的点
第一种是以x为中心的回文串全部包含于以k为中心的回文串中，此时直接将red[x]赋值给red[i]，x的值在图中有求
另一种是不完全包含，由于不知道k回文串之后的字符，所以不能莽撞的进行直接赋值，只能保留在字符串k以内的部分，即棕色部分，这部分的长度就是red[k]+k-i。问题解决。
第二次做这个题时，怎么写都是RE，死活改不过来
于是请来了外援ZlycerQan，不过五分钟，发现了错误%%%
define的用法不懂，在这个题中如果define MAXN 110000+10
那么在以后调用的过程中如果写成MAXN*2，实际上是110000+10*2，空间就不够了
#include<iostream> #include<cstdio> #include<cstring> #define INF 99999999 using namespace std; const int MAX=110000+10; char s[MAX*2]; int red[MAX*2]; int main(){ while(scanf("%s",s)!=EOF){ int len=strlen(s),k=0,maxlen=0; for(int i=len;i>=0;--i){//插入'#' s[i+i+2]=s[i]; s[i+i+1]='#'; }//插入了len+1个'#',最终的s长度是1~len+len+1即2*len+1,首尾s[0]和s[2*len+2]要插入不同的字符 s[0]='*';//s[0]='*',s[len+len+2]=' ',防止在while时red[i]越界 for(int i=2;i<2*len+1;++i){ if(red[k]+k>i)red[i]=min(red[2*k-i],red[k]+k-i); else red[i]=1; while(s[i-red[i]] == s[i+red[i]])++red[i]; if(k+red[k]<i+red[i])k=i; if(maxlen<red[i])maxlen=red[i]; } cout<<maxlen-1<<endl; } return 0; }