回文的判断
回文数作为一种有着特别性质的数,自然是出题人钟爱的类型,那么,我们应该如何判断呢回文字符串呢?
实际上最朴素的办法就是挨个枚举中间点
表面上看似O(n^2)
实际上更加复杂
为什么呢?
因为回文子串有两种:
- 奇数回文,以一个字符为中心
- 偶数回文,以中间空格为中心
Manacher算法
Manacher?
老牛拉破车马拉车算法
Manacher
为马拉车
(手动滑稽)- 偶数回文的处理方法
- 当前的位置不在已知回文串内
偶数串回文
实际上这个问题是非常好解决的,我们将其中的空隙全部加上相同的符号,问题就被成功的解决了qwq
越界
这问题可谓是相当的好解决与不好解决了,我们会遇到的有三种情况
- 回文已知长度在最右边界内 这种状况直接找
- 回文长度超过边界 这个时候我们就要注意我们能够推理出来的长度只能到达边界,后面之内去找
- 当前位置不在已知回文串内 这个就只能从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写,常数过大