-
2022-01-20 22:27:32
算法介绍
马拉车算法是用来在一个字符串中寻找最长回文串(正着读和反着读都相同的字符串)的一种算法。
该算法运用了动态规划的思想,将寻找最长回文串算法的时间复杂度降低到了线性。算法原理
对于一个字符串要判断它是否为回文串要分为字符串长度为奇数或者偶数两种情况,为了简化做法,我们进行如下的操作:
- 在字符串的两端和每两个字符中间添加一个 ‘#’ (或者任意一个一定不会在字符串中出现的字符, 通常就是 ‘#’ 啦)
- 再在字符串的开始和结尾放置字符串开始和结束的标识符。
上述操作后拓展出来的字符串的长度一定是奇数。
例如:
abcd 拓展后变为 ^#a#b#c#d#$ abc 拓展后变为 ^#a#b#c#$
要将算法的复杂度降低到线性,我们就要用到动态规划的思想。
这里我们定义了一个dp数组,其中dp[i]定义为以下标为i的字符作为回文串中心的回文半径 (从中心元素到左边界或右边界的字符长度) 的大小。这里举个例子 s[] = "abac" str[] ^ # a # b # a # c # $ dp[] 1 2 1 4 1 2 1 2 1
我们得出dp数组后问题就可以解决了,所以接下来就是要着力求解dp数组了。
动态规划的核心便是通过之前的计算来简化之后要进行的计算,我们这里再引入两个量来实现这个过程:int right; // 在计算过程中用于记录寻找到所有子回文串中右边界的下标 int pos; // 用于记录右边界就是right的子回文串的下标
接下来就是算法的关键了我们要逐次求出dp[i]的值:
我们在计算dp[i]时首先考虑这个值之前是否计算过,这里要充分利用回文串的特点。---------------------------------------------------- ^ ^ ^ |<--------------------|-------------------->| left pos right
如果 i 在 pos 和 right 之间,则可以寻找 i 关于 pos 的对称点,这时可以先假设
dp[i] = dp[2*pos-i]
,这个假设并不在任何情况下都成立:
如果中心为 2*pos-i 的回文串覆盖的区域左边界超过了left,则这个回文串中存在一些可能不在中心为 i 的回文串中的元素,这种情况下dp[i] = right-i
将上述讨论的情况结合起来即可得到:
dp[i] = min(dp[2*pos-i], right-i)
如果i > right
那我们就用暴力的方法求解dp[i]即可算法实现
int Manacher(char* s) { int len = strlen(s+1); char str[2*len+10]; int dp[2*len+10]; int cur = 0; str[0] = '^'; for(int i = 0; i < len; ++i) { str[++cur] = '#'; str[++cur] = s[i]; } str[++cur] = '#', str[++cur] = '$'; int right = 0, pos = 0; for(int i = 1; i <= cur; ++i) { if(i < right) dp[i] = min(dp[2*pos-i], right-i); else dp[right=i] = 1; while(str[i-dp[i]] == str[i+dp[i]]) ++dp[i]; if(i+dp[i] > right) right = i+dp[i], pos = i; } return *max_element(dp+1, dp+cur+1)-1; }
特别感谢
感谢我女朋友对我的大力支持😘。
更多相关内容 -
马拉车算法介绍
2018-04-12 21:37:55该文档是对马拉车算法的自己的认识,用了较为简易的文字进行了描述,关于马拉车算法,是专门用于求时间复杂度为O(n)的回文子串的算法。 -
马拉车算法(Manacher's Algorithm)
2021-03-15 14:37:46这是悦乐书的第343次更新,第367篇原创Manacher's Algorithm,中文名叫马拉车算法,是一位名叫Manacher的人在1975年提出的一种算法,解决的问题是求最长回文子串,神奇之处在于将算法的时间复杂度精进到了O(N),下面...这是悦乐书的第343次更新,第367篇原创
Manacher's Algorithm,中文名叫马拉车算法,是一位名叫Manacher的人在1975年提出的一种算法,解决的问题是求最长回文子串,神奇之处在于将算法的时间复杂度精进到了O(N),下面我们来详细介绍下这个算法的思路。
01 算法由来
在求解最长回文子串的问题时,一般的思路是以当前字符为中心,向其左右两边扩展寻找回文,但是这种解法的时间复杂度是O(N^2),那么能不能将时间复杂度再降低一点?做到线性?马拉车算法就完美地解决了这个问题。
02 预处理
回文字符串以其长度来分,可以分为奇回文(其长度为奇数)、偶回文(其长度为偶数),一般情况下需要分两种情况来寻找回文,马拉车算法为了简化这一步,对原始字符串进行了处理,在每一个字符的左右两边都加上特殊字符(肯定不存在于原字符串中的字符),让字符串变成一个奇回文。例如:
原字符串:abba,长度为4
预处理后:#a#b#b#a#,长度为9
原字符串:aba,长度为3
预处理后:#a#b#a#,长度为7
03 计算最长回文子串长度
以字符串"cabbaf"为例,将预处理后的新字符串"#c#a#b#b#a#f#"变成一个字符数组arr,定义一个辅助数组int[] p,p的长度与arr等长,p[i]表示以arr[i]字符为中心的最长回文半径,p[i]=1表示只有arr[i]字符本身是回文子串。
i 0 1 2 3 4 5 6 7 8 9 10 11 12
arr[i] # c # a # b # b # a # f #
p[i] 1 2 1 2 1 2 5 2 1 2 1 2 1
我们来比对分下一下最长回文半径和原字符串之间的关系。在上面例子中,最长回文子串是"#a#b#b#a#",它以arr[6]为中心,半径是5,其代表的原始字符串是"abba",而"abba"的长度为4,可以通过5减去1得到,是字符串"cabbaf"中的最长回文子串,那么我们是不是可以得出最长回文半径和最长回文子串长度之间的关系?
让我们再多看几个例子,如"aba",转换后是"#a#b#a#",以字符'b'为中心的回文,半径是4,减1得到3,3是原字符串的最长回文子串长度。
再例如"effe",转换后是"#e#f#f#e#",以最中间的'#'为中心的回文,半径是5,减1得到4,4是原字符串的最长回文子串长度。
因此,最后我们得到最长回文半径和最长回文子串长度之间的关系:int maxLength = p[i]-1。maxLength表示最长回文子串长度。
04 计算最长回文子串起始索引
知道了最长回文子串的长度,我们还需要知道它的起始索引值,这样才能截取出完整的最长回文子串。
继续以第三步中的字符串"cabbaf"为例,p[6]=5,是最长半径,用6(i)减去最长半径5(p[i])得到1,而1恰好是最长回文子串"abba"的起始索引。
我们再来看一个奇回文的例子。例如"aba",转换后是"#a#b#a#",p[3]=4,最长半径是4,i为3,用i减去4得到-1,数组下标越界了。
在偶回文的情况下,可以满足i减最长半径,而奇回文却会下标越界,我们需要在转换后的字符串前面再加一个字符,解决下标越界的问题,不能是'#',那就加个'$'字符吧,但是加过一个字符后,字符串的长度不是奇数了,只能在尾部再加一个不会重复出现的字符,比如'@',这样字符串的长度依旧是奇数了,满足前面第三部分的条件。
加多一个字符后,奇回文可以正常做减法了,偶回文呢?
i 0 1 2 3 4 5 6 7 8 9 10 11 12 13
arr[i] $ # c # a # b # b # a # f #
p[i] 1 2 1 2 1 2 5 2 1 2 1 2 1
在补上字符'$'后,p[7]=5,用i减去最长半径,7-5=2,而理想的结果应该是1,那就再除以2吧,这样就能得到1了。而奇回文"aba"在用i减去最长半径后得到的是0,除以2后还是0,可以完美解决下标越界的问题。
结论:最长回文子串的起始索引int index = (i - p[i])/2。
05 计算p数组
在第三步和第四步中我们都用到了一个关键对象p数组,存放的是最长回文子串半径,那么它是怎么来的呢?
还是以上面的例子配合着看,
i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
arr[i] $ # c # a # b # b # a # f # @
p[i] 1 2 1 2 1 2 5 2 1 2 1 2 1
设置两个变量id和mx,id是所有回文子串中,能延伸到最右端位置的那个回文子串的中心点位置,mx是该回文串能延伸到的最右端的位置。
当i等于7时,id等于7,p[id] = 5,在以位置7为中心的回文子串中,该回文子串的右边界是位置12。
当i等于12时,id等于12,p[id] = 2,在以位置12为中心的回文子串中,该回文子串的右边界是位置14。
由此我们可以得出回文子串右边界和其半径之间的关系:mx = p[id]+id。
image
因为回文字符串是中心对称的,知道中心点位置id,如果一个位置的回文子串以i为中心,并且包含在以id为中心的回文子串中,即mx > i,那么肯定会存在另外一个以j为中心回文子串,和以i为中心的回文子串相等且对称,即p[j] = p[i],而i和j是以id为中心对称,即i+j=2*id,如果知道了i的值,那么j = 2*id - i。
但是我们需要考虑另外一种情况,如果存在一个以i为中心的回文子串,依旧有mx > i,但是以i为中心的回文子串右边界超过了mx,在i到mx的这段回文子串中,与另一端对称的以j为中心的回文子串还是相等的,此时p[i] = mx - i,p[j] = [pi],至于右边界mx之外的子串,即以i为中心的回文子串超出的部分是否还是满足上述条件就需要遍历比较字符了。
因此,在mx > i的情况下,p[i] = Math.min(p[2*id - i], mx - i)。
另外如果i大于mx了,也即是边界mx后面的子串,依旧需要去比较字符计算。
public static String Manacher(String s) {
if (s.length() < 2) {
return s;
}
// 第一步:预处理,将原字符串转换为新字符串
String t = "$";
for (int i=0; i
t += "#" + s.charAt(i);
}
// 尾部再加上字符@,变为奇数长度字符串
t += "#@";
// 第二步:计算数组p、起始索引、最长回文半径
int n = t.length();
// p数组
int[] p = new int[n];
int id = 0, mx = 0;
// 最长回文子串的长度
int maxLength = -1;
// 最长回文子串的中心位置索引
int index = 0;
for (int j=1; j
// 参看前文第五部分
p[j] = mx > j ? Math.min(p[2*id-j], mx-j) : 1;
// 向左右两边延伸,扩展右边界
while (t.charAt(j+p[j]) == t.charAt(j-p[j])) {
p[j]++;
}
// 如果回文子串的右边界超过了mx,则需要更新mx和id的值
if (mx < p[j] + j) {
mx = p[j] + j;
id = j;
}
// 如果回文子串的长度大于maxLength,则更新maxLength和index的值
if (maxLength < p[j] - 1) {
// 参看前文第三部分
maxLength = p[j] - 1;
index = j;
}
}
// 第三步:截取字符串,输出结果
// 起始索引的计算参看前文第四部分
int start = (index-maxLength)/2;
return s.substring(start, start + maxLength);
}
06 小结
马拉车算法将求解最长回文子串的时间复杂度降低到了O(N),虽然也牺牲了部分空间,其空间复杂度为O(N),但是其算法的巧妙之处还是值得学习和借鉴的。
算法专题目前已连续日更超过六个月,算法题文章211+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。
以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,好看、留言、转发就是对我最大的回报和支持!
-
马拉车算法
2021-04-07 22:35:39Manacher 算法 ,用以求解最长回文字符串,其时间复杂度为o(n), 这个算法首先最帅的一点在于对奇偶字符串的处理,例如aba和abba,那么仅仅需要在每个字符之间(包括外层)插入一个原字符串没有的字符,一般用“#”...Manacher 算法 ,用以求解最长回文字符串,其时间复杂度为o(n),
这个算法首先最帅的一点在于对奇偶字符串的处理,例如aba和abba,那么仅仅需要在每个字符之间(包括外层)插入一个原字符串没有的字符,一般用“#”或者“$”,此时aba变成了:
#a#b#a# 仍是以b为中心的奇数长度回文字符串
此时abba变成了:
#a#b#b#a#这是其变成了以“#”为中心的奇数长度回文字符串
有了以上的处理就可以将奇偶字符串统一拓展为奇数长度字符串进行处理。
但是manacher 算法中对字符串的处理还要进行防止越界处理(具体原因见下文处理)
比如对abba字符串的处理(注意下标)
a b b a 其下标为:
0 1 2 3预处理后的字符串
@#a#b#b#a#$ 其下标为
0 1 23456789 10
1.我们处理过的要用的字符串从下标从1 开始
2.为防止越界要在新字符串下标为0的位置 和字符串的末尾添加两个原来串没有又不同的字符
我这里用的就是@ 和 $
下面贴预处理的代码
void pre_change() { newstr[0] = '@' ; newstr[1] = '#' ; for(int i = 0 ; i < len ; i ++ ) { newstr[2*i + 2 ] = str[i] ; newstr[2*i + 3 ] = '#' ; } newstr[2 * len + 2 ] = '$' ; return ; }
这样就预处理完毕了,接下来是该最精彩的部分 ;
用一个数组 r [i] 记录 以newstr[i]为中心的最长回文串的半径长度
r[i]数组是马拉车算法的核心!!!!
用 maxid 记录 在位置 i 以前的回文串右边能延伸到的最大位置
即maxid = id + r[id] ;
id 即对应maxid
注意这个id 不是 i 而是之前某个位置的下标 !
然后就用了动态规划的思想以o(n)的复杂度更新了所有的newstr[i] 对应的r[i] ;
接下来先看代码!
void Manacher() { int id , maxid = 0 ; len = 2 * len + 2 ; for(int i = 0 ; i < len ; i ++ ) { if(maxid > i ) r[i] = min(r[2 * id - i] , maxid - i ) ; else r[i] = 1 ; while(newstr[i + r[i]] == newstr[i - r[i]]) r[i] ++ ; if( r[i] + i > maxid) { maxid = r[i] + i ; id = i ; } } }
先看看动态规划更新r[i]的核心部分
for(int i = 0 ; i < len ; i ++ ) { if(maxid > i ) r[i] = min(r[2 * id - i] , maxid - i ) ; else r[i] = 1 ;
如上图由 已知可以知道 j = 6 , i = 14 , maxid = mi = 17 , id = 10 ;
可以明显看出r[i] = 4 ,即11到i
r[j] = 6 ; 即j 到11
j 是i 关于id对称位置的下标
并且有j = 2 * id - i ;
根据对称原理可知
若newstr[j]处有回文串 , 则其对称位置newstr[i]处最大回文串半径r[i] = r[j] ;
如上图这里j处对称过来的回文串长度 加上i的坐标显然超过了mi 即 maxid ,这时r[i]只需要取mi - i 即可
即有状态转移方程 r[i] = min(r[j] , maxid - i) ;
即上面核心代码maxid > i的部分
若maxid < i,很显然在 i 并不在回文串id -maxid 到id + maxid内,此时newstr[i]只能跟自己构成回文串了,故r[i] = 1 ; 然后是
while(newstr[i + r[i]] == newstr[i - r[i]]) r[i] ++ ;
直接更新位置i处的回文串半径,不再赘述。
最后有
while(newstr[i + r[i]] == newstr[i - r[i]]) r[i] ++ ; if( r[i] + i > maxid) { maxid = r[i] + i ; id = i ; }
如上文所述 maxid为i前回文串向后延伸的最远位置 ,若i处向后延伸的回文串还能更远,那么更新
maxid ,这时候id 就更新为 i 。
经过如上面的一轮循环,我们就找到了字符串中关于每个位置i的最大回文串半径r[i] !!!!
设L[i]为x新字符串中以newstr[i]为中心的最长回文串长度
那么显然有 L[i] = 2 * r[i] - 1
容易知道 L[i]的长度总为奇数字符串的长度
对于两种字符串 #a#b#a#或#a#a#
其对应的回文串长度(L -1)/2 即为原来的字符串长度!
该值为r[i] - 1 !!!
那么想要找到这一个字符串中最长的回文串的长度,不断更新r[i] - 1的最大值即可!!
于是用来求最长回文串长度的代码如下
void Manacher() { int max_len = 0 ; int id , maxid = 0 ; len = 2 * len + 2 ; for(int i = 0 ; i < len ; i ++ ) { if(maxid > i ) r[i] = min(r[2 * id - i] , maxid - i ) ; else r[i] = 1 ; while(newstr[i + r[i]] == newstr[i - r[i]]) r[i] ++ ; if( r[i] + i > maxid) { maxid = r[i] + i ; id = i ; } max_len = max(max_len,r[i] - 1 ); } printf("%d\n",max_len) ; }
以上就是马拉车算法的教程,有一说一马老先生是真的NB!
-
关于马拉车算法
2020-10-29 15:19:33马拉车算法用于解决回文串问题,个人经常会忘记其原理,所以在此整理一下。 对于回文串,简单说即正着念和反着念是一样的字符串,如abba。用常规的暴力方法,即以一个字符为中心,两边分别外扩,比较每个字符。这种...马拉车算法用于解决回文串问题,个人经常会忘记其原理,所以在此整理一下。
对于回文串,简单说即正着念和反着念是一样的字符串,如abba。用常规的暴力方法,即以一个字符为中心,两边分别外扩,比较每个字符。这种方法需要分奇偶来讨论,即如aba和abba这两种情况。
1.马拉车算法首先需要对字符串进行处理,在字符串开头结尾及字符间穿插同一个特殊字符,该字符可以是任何字符,不影响结果。
处理后的字符串,不管原字符串长度是奇是偶,都变成了奇,这样就可以以同一种方式处理了。
2.这里引入两个变量,分别是R和C。下面将解释两个变量的意义。
假设下图方框表示以a为中心的回文字符串
我们用一个数组array来表示对以应位置的字符为中心,其最长的回文字符串长度。即array[7] = 8。那么我们知道,在以a为中心的回文字符串中,因为对称的关系,左右两边有着相同的子串
依照这个特性,后面字符的array值,是可以参考前面对称位置字符的array值的。R的作用是框定当前回文半径最长的距离(只增不减),即上图14的位置,而c则是以R为半径的回文串中心。这里分两种情况。
(1)若当前i的位置小于R(即如上图在红框内),则以其对称位置2c-i的array值为基础,再向外扩展。
(2)若i大于R,即在红框外,array初始值设为1,则需要按照之前的方式,两边展开来比较,无优化。比较完后再更新R和C值。//预先处理字符串 string getmancher(string str) { string res(2*str.length()+1,0); int j = 0; for(size_t i = 0;i<str.length();i++) { res[j] = '#'; res[j+1] = str[i]; j = j+2; } res[2*str.length()]= '#'; return res; } int maxbackstr(string str) { int Max = INT32_MIN; int R = -1; int C = -1; int array[str.length()]; for(int i = 0;i<str.length();i++) { array[i] = i>=R?1:min(array[2*C-i],R-i-1); while(i+array[i]>=0 && i+array[i]<str.length()){ if(str[i-array[i]] == str[i+array[i]]) array[i]++; else break; } if(R<i+array[i]-1){ R = i+array[i]-1; C = i; } Max = max(Max,array[i]); } return Max-1; } int main() { string str = "abba"; cout<<maxbackstr(getmancher(str))<<endl; return 0; }
对字符串要进行遍历,由于R不会回退,故时间复杂度为O(n)。
-
Manacher算法详细解析 (马拉车算法)
2022-02-05 13:48:45应用场景: 如求最长回文子串的题目,或者结合其他算法求解算法题目时可以用到。 ... Mediocre String Problem(马拉车+拓展KMP)https://blog.csdn.net/weixin_44134344/article/details/1100... -
动态规划之马拉车算法(Python解法)
2020-08-20 04:01:45本篇文章主要介绍我个人对马拉车算法实现思路的一些想法,原题解请看leetcode-647.回文子串 中心拓展法 对于这个问题,简单的做法是枚举字符串中的每个子串,然后判断子串中回文串的个数。 由于回文串有对称性这... -
浅谈字符串匹配算法——马拉车算法(Manacher‘s Algorithm)
2021-05-17 23:54:09LeetCode - 最长回文串 简书马拉车 https://www.jianshu.com/p/392172762e55 https://zhuanlan.zhihu.com/p/70532099 这个算法的总框架是,遍历所有的中心点,寻找每个中心点对应的最长回文子串,然后找到所有... -
最长回文子串——马拉车算法
2020-03-06 14:16:32针对最长回文子串相关的问题,马拉车算法应该是比较通用的解法,今天我们就来具体看看这个算法。 简介 马拉车算法(Manacher‘s Algorithm)是用来查找一个字符串的最长回文子串的线性方法,由一个叫 Manacher 的人... -
Manacher's Algorithm 马拉车算法
2019-03-11 23:08:50这个马拉车算法Manacher‘s Algorithm是用来查找一个字符串的最长回文子串的线性方法,由一个叫Manacher的人在1975年发明的,这个方法的最大贡献是在于将时间复杂度提升到了线性,这是非常了不起的。对于回文串想必... -
Manacher's Algorithm 马拉车算法(C++)
2019-06-05 00:08:32Manacher’s Algorithm 马拉车算法 什么鬼名字? 参考以下链接,把java代码用c++写了一遍 最长回文字符串算法-Manacher’s Algorithm-马拉车算法 算法介绍 这个马拉车算法Manacher‘s Algorithm是用来查找一个字符... -
最长回文子串——马拉车算法(Manacher‘s Algorithm)总结
2020-10-19 18:32:21文章目录马拉车算法(Manacher's Algorithm)算法由来算法流程1、对原始字符串进行预处理(添加分隔符)2、计算辅助数组 ppp(回文半径数组)3、计算最长回文子串起始索引4、如何高效地计算数组 ppp 马拉车算法... -
manacher(马拉车算法)过程及python代码实现
2020-04-14 21:13:15manacher(马拉车算法)过程及python代码实现 问题应用 回文子串的寻找 回文串特点 奇回文:aba 偶回文:abba 变量定义 mx:所有已知右边界中最靠右的位置 id:mx对应的中心点 p[]:以当前index为中心,s'... -
Manacher算法(马拉车算法)
2018-08-28 11:18:34Manacher算法利用一个辅助数组P[i]表示以字符Str[i]为中心的最长回文子串的最右(左)字符到Str[i]的距离(包括Str[i]) 以abbc为例,首先预处理变成:$#a#b#b#c# (预处理是为了便于处理)可... -
马拉车算法(Manacher)
2019-07-28 15:50:56马拉车算法分为几个步骤: 1.字符中插入特殊字符,通常插入"#",插入后字符串必会变成一个奇数串,因为插入的字符个数是len+1。首尾加上不同的字符例如&¥,简化边界情况越界判断。 2.计算半径数组p 3.数组p中... -
(AC)Manacher Algorithm 马拉车算法(Java)
2019-02-08 21:17:26方法一:马拉车算法 时间复杂度O(n) 这个算法最为关键的一行 r[i] = mx > i ? Math.min(r[2 * id - i], mx - i) : 1; 具体讲解传送门。 基本上理解了这句·就差不多懂了90% 最后根据找到的最大回文... -
Manacher's Algorithm-马拉车算法-JavaScript实现
2019-03-20 15:09:12关于马拉车算法 马拉车算法:Manacher‘s Algorithm是用来查找一个字符串的最长回文子串的线性方法,由一个叫Manacher的人在1975年发明的,这个方法的最大贡献是在于将时间复杂度提升到了线性,时间复杂度为O(n)... -
【算法】——Manacher Algorithm(马拉车算法)
2018-09-02 23:33:45一、马拉车算法来源 马拉车算法Manacher‘s Algorithm是用来查找一个字符串的最长回文子串的线性方法,由一个叫Manacher的人在1975年发明的,这个方法的最大贡献是在于将时间复杂度提升到了线性,这是非常了不起的... -
最长回文子串——马拉车算法详解
2018-09-12 06:52:44马拉车算法(Manacher‘s Algorithm)是用来解决求取一个字符串的最长回文子串问题的。此算法充分利用了回文字符串的性质,将算法复杂度降到了线性,非常值得一学。 我将网上所有讲解马拉车算法的文章基本看了一遍...