回文串定义:“回文串”是一个正读和反读都一样的字符串,比如“level”或者“noon”等等就是回文串。
回文子串,顾名思义,即字符串中满足回文性质的子串。
经常有一些题目围绕回文子串进行讨论,比如 HDOJ_3068_最长回文,求最长回文子串的长度。朴素算法是依次以每一个字符为中心向两侧进行扩展,
显然这个复杂度是 O(N^2)的,关于字符串的题目常用的算法有 KMP、后缀数组、 AC 自动机,这道题目利用扩展 KMP可以解答,其时间复杂度也很快 O(N*logN)。
但是,今天笔者介绍一个专门针对回文子串的算法,其时间复杂度为 O(n),这就是 manacher 算法。
大家都知道,求回文串时需要判断其奇偶性,也就是求 aba 和 abba 的算法略有差距。然而,这个算法做了一个简单的处理,很巧妙地把奇数长度回文串与偶数长度回文串统一考
虑,也就是在每个相邻的字符之间插入一个分隔符,串的首尾也要加,当然这个分隔符不能再原串中出现,一般可以用‘#’或者‘$’等字符。例如:
原串:abaab
新串:#a#b#a#a#b#
这样一来,原来的奇数长度回文串还是奇数长度,偶数长度的也变成以‘#’为中心的奇数回文串了。
接下来就是算法的中心思想,用一个辅助数组 P 记录以每个字符为中心的最长回文半
径,也就是 P[i]记录以 Str[i]字符为中心的最长回文串半径。 P[i]最小为 1,此时回文串为 Str[i]本身。
我们可以对上述例子写出其 P 数组,如下
新串: # a # b # a # a # b #
P[] : 1 2 1 4 1 2 5 2 1 2 1
我们可以证明 P[i]-1 就是以 Str[i]为中心的回文串在原串当中的长度。
证明:
1、显然 L=2*P[i]-1 即为新串中以 Str[i]为中心最长回文串长度。
2、以 Str[i]为中心的回文串一定是以#开头和结尾的,例如“#b#b#”或“#b#a#b#”所以 L 减去最前或者最后的‘#’字符就是原串中长度的二倍,即原串长度为(L-1)/2,化简
的 P[i]-1。得证。
依次从前往后求得 P 数组就可以了,这里用到了 DP(动态规划)的思想,也就是求 P[i]的时候,前面的 P[]值已经得到了,我们利用回文串的特殊性质可以进行一个大大的优化。
核心代码:
// MaxId为i字符之前最大回文串向右延伸的最大位置
// id为MaxId对应的最大回文串的中心位置
for(int i = 1;i < len;i++){
//初步定i位置字符为中心的半径
if(MaxId > i){
p[i] = min(MaxId - i,p[2*id - i]);
}
else{
p[i] = 1;
}
//继续确定i位置字符为中心的半径 这地方用到'$'
while(str[i-p[i]] == str[i+p[i]]){
p[i]++;
}
//更新MaxId,id
if(p[i]+i > MaxId){
MaxId = p[i] + i;
id = i;
}
}
为了防止求 P[i]向两边扩展时可能数组越界,我们需要在数组最前面和最后面加一个特殊字符,令 P[0]= ‘$’最后位置默认为‘\0’不需要特殊处理。此外,我们用 MaxId 变量
记录在求 i 之前的回文串中延伸至最右端的位置,同时用 id 记录取这个 MaxId 对应回文串的中心位置。
通过下面这句话,算法避免了很多没必要的重复匹配。
if(MaxId>i)
{
p[i]=min(p[2*id-i],MaxId-i);
}
那么这句话是怎么得来的呢,其实就是利用了回文串的对称性,如下图,
j=2*id-i 即为 i 关于 id 的对称点,根据对称性,P[ j]的回文串也是可以对称到 i 这边的,但是如果 P[ j]的回文串对称过来以后超过 MaxId 的话,超出部分就不能对称过来了,如下
图,所以这里 P[i]为的下限为两者中的较小者,p[i]=Min(p[2*id-i],MaxId-i) 。
算法的有效比较次数为 MaxId 次,所以说这个算法的时间复杂度为 O(n)。
这是我具体实现的代码:
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
//数据预处理
char* Init(char* s){
int len = strlen(s);
char* str = new char(2*len+4);
str[0] = '$';
int index = 1;
for(int i = 0;i < len;i++){
str[index++] = '#';
str[index++] = s[i];
}
str[index++] = '#';
str[index] = '\0';
return str;
}
string MaxPalindromeNumber(char* s){
char *str = Init(s);
int maxId = 0,center = 1;
int len = strlen(str);
int *p = new int[len+1];
// MaxId为i字符之前最大回文串向右延伸的最大位置
// id为MaxId对应的最大回文串的中心位置
for(int i = 1;i < len;i++){
//初步定i位置字符为中心的半径
if(maxId > i){
p[i] = min(maxId - i,p[2*center - i]);
}
else{
p[i] = 1;
}
//继续确定i位置字符为中心的半径 这地方用到'$'
while(str[i-p[i]] == str[i+p[i]]){
p[i]++;
}
//更新MaxId,id
if(p[i]+i > maxId){
maxId = p[i] + i;
center = i;
}
}
// 最大长度
int maxLen = 0;
center = 1;
for(int i = 1;i < len;i++){
if(str[i] != '#' && p[i] - 1 > maxLen){
maxLen = p[i] - 1;
center = i;
}
}
//提取最大回文串
char* maxStr = new char[maxLen+1];
int index = 0;
for(int i = center - maxLen;i <= center + maxLen;i++){
if(str[i] != '#'){
maxStr[index++] = str[i];
}
}
maxStr[index] = '\0';
return maxStr;
}
int main(){
char* str="skjflkdsjfkldsababasdlkfjsdwieowowwpw";
cout<<MaxPalindromeNumber(str);
return 0;
}
分享到:
相关推荐
当 mx - i > P[j] 的时候,以S[j]为中心的回文子串包含在以S[id]为中心的回文子串中,由于 i 和 j 对称,以S[i]为中心的回文子串必然包
查找一个字符串中的最长回文子串,这里采用的是Manacher算法 比如:cababcaac的最长回文子串就是caac 其中的aba bab也都是回文子串 (Manacher算法) 效率很高的一种查找算法,效率可以达到O(2n+1)
ACM比赛模板积累,Manacher算法,时间复杂度O(n),可适应于求输入串的最长回文子串
Manacher算法:求解最长回文字符串,时间复杂度为O(N) 回文串定义:“回文串”是一个正读和反读都一样的字符串,比如“level”或者“noon”等等就是回文串。回文子串,顾名思义,即字符串中满足回文性质的子串。
4.2.3 使用Manacher算法求最长回文子串.pdf
求回文比较好的一种算法,很值得了解与学习
文章目录最长回文子串获取最长回文子串暴力遍历最长回文字符串相应代码Manacher算法相应代码末尾添加最短字符串构成回文串算法思路相应代码 最长回文子串 获取最长回文子串 【题目】 给定一个字符串str,返回str中...
答案当然是肯定的,那就是中心扩展法,选择一个元素作为中心,然后向外发散的寻找以该元素为圆心的最大回文子串。但是又出现了新的问题,回文子串的长度即可能是基数,也可能好是偶数,对于长度为偶数的回文子串来说...
Manacher算法是一位名叫Manacher的人在1975年提出的一种算法,解决的问题是求最长回文子串。Manacher算法的核心思路就是利用之前求得的臂长( 即之前求出的Len值) 来减少时间复杂度,也就是说通过前面求出的Len值来...
该文档是对马拉车算法的自己的认识,用了较为简易的文字进行了描述,关于马拉车算法,是专门用于求时间复杂度为O(n)的回文子串的算法。
KMP(字符串匹配),Trie树(字典树),manacher(最长回文子串) 算法思想 代码 经典题目
2 8 字符串的最长回文子串:Manacher 算法 42 第 3 章 序列 44 3 1 网格中的最短路径 44 3 2 编辑距离(列文斯登距离45 3 3 最长公共子序列 47 3 4 升序最长子序列 49 3 5 两位玩家游戏中的必胜策略 52 第 4 章 数组...
Manacher:找到最长回文子串 Ukkonen的后缀树构造非常复杂。 仅在有时间时学习。 图/树算法 核心 树遍历LC1457 , 循环检测LC684 , LC207 最小生成树 Dijkstra算法LC743 统一成本搜索Dijkstra的算法搜索从根...
数据结构 后缀数组 后缀自动机 splay link-cut tree 可持久化treap ...Manacher回文子串 字符串最小表示 其它 树的hash 梭哈牌型的比较函数 麻将 最大团的搜索算法 FFT (非递归) FFT 混合基 表达式计算
最长回文子串(manacher) 1323 回文字符串(dp增删字符) 1326 有序01字符串AC 1361 Playfair密码表 AC 1485 hiho字符串AC(滑动窗口) 恰好包含的最小长度 1485 LeetCode76滑动窗口 包含子串的最小长度 1566 皇室...
最长回文子串 Manacher 算法: 合并两个排序列表 3总和 电话号码的字母组合 特殊二进制字符串 有效的括号字符串 合并 K 个排序列表 帕斯卡三角形 帕斯卡三角形 II 截留雨水 收集雨水 II 递增三重子序列 买卖股票的...
最长回文子串(Manacher 算法) 线性字符串旋转到位 数学技巧 使用 sqr fxn(快速逆平方根 - 恒定时间)查找 w/o 元素的平方根: DP 寻找具有最大和的连续子数组(Kadane 算法): 钾 查找第 K 个最大元素: K总和:...
最长回文子串 (316 毫秒) 上) 上) 使用 Manacher 算法 问题 201-250 # 标题 解决方案 时间 空间 注释 222 计算完整的树节点 (0 毫秒) O(log 2 N) O(1) 问题 251-300 # 标题 解决方案 时间 空间 注释 287 找到...
最长回文子串 中(整理Manacher笔记,改进蛮力法) 二分搜索和日志(n)算法(Lintcode) # 标题 困难 458 没有任何 没有任何 585 山地序列中的最大数 中等的 460 找到 K 个最近的元素 中等的 447 没有任何 没有任何...