POJ 3974 Palindrome 回文子串 — 初学Manacher算法

回文的判断 回文数作为一种有着特别性质的数,自然是出题人钟爱的类型,那么,我们应该如何判断呢回文字符串呢? 实际上最朴素的办法就是挨个枚举中间点 表面上看似O(n^2) 实际上更加复杂 为什么呢? 因为回文子串有两种:

  1. 奇数回文,以一个字符为中心
  2. 偶数回文,以中间空格为中心
所以我们除了遍历数字,还要遍历空格… 显然这种算法耗时太大了,我们需要对其进行优化,于是就有了我们今天的主题:Manacher算法

Manacher?

老牛拉破车马拉车算法
为了语言方便,下文全部称Manacher马拉车(手动滑稽) 我们知道回文字符串有着对称性,也就是说,如果目前已知的回文子串中,左边还有一个回文子串,那么右边也会有一个相同长度的回文子串 这样一来,我们的中间的遍历过程会少许多,因为在知道了对称状况下,就可以知道目前以这个位置展开的回文子串最小长度 但是这个方法随之而来的还有两个问题:
  • 偶数回文的处理方法
  • 当前的位置不在已知回文串内

偶数串回文


实际上这个问题是非常好解决的,我们将其中的空隙全部加上相同的符号,问题就被成功的解决了qwq

越界


这问题可谓是相当的好解决与不好解决了,我们会遇到的有三种情况
  1. 回文已知长度在最右边界内 这种状况直接找
  2. 回文长度超过边界 这个时候我们就要注意我们能够推理出来的长度只能到达边界,后面之内去找
  3. 当前位置不在已知回文串内 这个就只能从1开始找了…
代码:
int mlc(char *a){// *a 要处理的字符串
                int len=strlen(a),blen=0;// len 处理字符串长度
                char b[2100000];
                memset(b,0,sizeof(b));//清空
                for(int i=0;i<len;i++){//加入#
                                b[blen++]='#';
                                b[blen++]=a[i];
                }
                b[blen++]='#';//别忘了结尾的
                int cen,mrig,reslen,rescen;// rescen已知最长的中间,reslen已知最长的长度,mrig最右端点,cen目前最右端点的重点
                cen=mrig=reslen=rescen=0;
                memset(p,0,sizeof(p));
                for(int i=0;i<blen;i++){
                                p[i]=mrig > i? min(p[2*cen-i],mrig-i) : 1;// 自己结合上文理解,算法核心
                                while(b[i+p[i]]==b[i-p[i]]&&i-p[i]>=0&&i+p[i]<blen) p[i]++;//开始模拟
                                if(mrig<i+p[i]) {//更新数值
                                                mrig=i+p[i];
                                                cen=i;
                                }
                                if(reslen<p[i]) {
                                                reslen=p[i];
                                                rescen=i;
                                }
                }
                return reslen-1;//别忘了减去#
}

题目

题目链接:[http://poj.org/problem?id=3974]
题目的大意就是求最长回文子串,对于这道题目,我们可以套取上面的算法模板 需要注意的是,尽可能不用STL写,常数过大

END

]]>