标签：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

]]>