【算法】——Manacher Algorithm（马拉车算法）

- 日理万妓 2022-05-14 04:43 209阅读 0赞

## **一、马拉车算法来源** ##

马拉车算法Manacher‘s Algorithm是用来查找一个字符串的[最长回文子串][Link 1]的线性方法，由一个叫Manacher的人在1975年发明的，这个方法的最大贡献是在于将时间复杂度提升到了线性，这是非常了不起的。对于回文串想必大家都不陌生，就是正读反读都一样的字符串，比如 "bob", "level", "noon" 等等，那么如何在一个字符串中找出最长回文子串呢，可以以每一个字符为中心，向两边寻找回文子串，在遍历完整个数组后，就可以找到最长的回文子串。但是这个方法的时间复杂度为O(n\*n)，并不是很高效，下面我们来看时间复杂度为O(n)的马拉车算法。

## 二、问题提出 ##

最坏的情况就是各个回文相互重叠的时候。例如"aaaaaaaaaa"和" cabcbabcbabcba"。

为什么说有重叠时是最坏的情况？因为会发生重复计算。★（换句话说，没有重叠时，必须要一点一点计算，也就没有可改进的余地了。）

花费一些空间来避免重复计算。★

利用回文的特性避免重复计算。★

## 三、算法剖析 ##

首先我们把字符串S改造一下变成T，改造方法是：在S的每个字符之间和S首尾都插入一个"\#"。这样做的理由你很快就会知道。

例如，S="abaaba"，那么T="\#a\#b\#a\#a\#b\#a\#"。

想一下，你必须在以Ti为中心左右扩展才能确定以Ti为中心的回文长度d到底是多少。（就是说这一步是无法避免的）

为了改进最坏的情况，我们把各个Ti处的回文半径存储到数组P，用P\[i\]表示以Ti为中心的回文长度。那么当我们求出所有的P\[i\]，取其中最大值就能找到最长回文子串了。

对于上文的示例，我们先直接写出所有的P研究一下。

显然最长子串就是以P\[6\]为中心的"abaaba"。

你是否发现了，在插入"\#"后，长度为奇数和偶数的回文都可以优雅地处理了？这就是其用处。

现在，想象你在"abaaba"中心画一道竖线，你是否注意到数组P围绕此竖线是中心对称的？再试试"aba"的中心，P围绕此中心也是对称的。这当然不是巧合，而是在某个条件下的必然规律。我们将利用此规律减少对数组P中某些元素的重复计算。

我们来看一个重叠得更典型的例子，即S="babcbabcbaccba"。

![o_longestPalindromicSubString01.png][]

上图展示了把S转换为T的样子。假设你已经算出了一部分P。竖实线表示回文"abcbabcba"的中心C，两个虚实线表示其左右边界L和R。你下一步要计算P\[i\]，i围绕C的对称点是i’。你有办法高效地计算P\[i\]吗？

我们先看一下i围绕C的对称点i’（此时i’=9）。

![o_longestPalindromicSubString02.png][]

据上图所示，很明显P\[i\]=P\[i’\]=1。这是因为i和i’围绕C对称。同理，P\[12\]=P\[10\]=0，P\[14\]=P\[8\]=0。

![o_longestPalindromicSubString03.png][]

现在再看i=15处。此时P\[15\]=P\[7\]=7？错了，你逐个字符检测一下会发现此时P\[15\]应该是5。

为什么此时规则变了？

![o_longestPalindromicSubString04.png][]

如上图所示，两条绿色实线划定的范围必定是对称的，两条绿色虚线划定的范围必定也是对称的。此时请注意P\[i’\]=7，超过了左边界L。超出的部分就不对称了。此时我们只知道P\[i\]>=5，至于P\[i\]还能否扩展，只有通过逐个字符检测才能判定了。

在此例中，P\[21\]≠P\[9\]，所以P\[i\]=P\[15\]=5。

我们总结一下上述分析过程，就是这个算法的关键部分了。

<table> 
 <tbody> 
  <tr> 
   <td style="vertical-align:top;"> <p><strong>if</strong>&nbsp;P[ i' ] &lt; R – i,</p> <p><strong>then&nbsp;</strong>P[ i ] ← P[ i' ]</p> <p><strong>else&nbsp;</strong>P[ i ] ≥ R - i. (此时要穿过R逐个字符判定P[i]).</p> </td> 
  </tr> 
 </tbody> 
</table>

是不是很优雅？如果你能理解到这里，你已经搞定了这个算法最困难也最精华的部分了。

很明显C的位置也是需要移动的，这个很容易：

<table> 
 <tbody> 
  <tr> 
   <td style="vertical-align:top;"> <p>如果i处的回文超过了R，那么就C=i，同时相应改变L和R即可。</p> </td> 
  </tr> 
 </tbody> 
</table>

每次求P\[i\]，都有两种可能。如果P\[i‘\] < R – i，我们就P\[i\] = P\[i’\]。否则，就从R开始逐个字符求P\[i\]，并更新C及其R。此时扩展R（逐个字符求P\[i\]）最多用N步，而求每个C也总共需要N步。所以时间复杂度是2\*N，即O(N)。

最近刷leetcode题目，正巧刷到最大回文串这题，折腾半天，发现马拉车这种神级算法，特此学习，做个记录，为日后翻看。本文参考来源：[http://www.cnblogs.com/bitzhuwei/p/Longest-Palindromic-Substring-Part-II.html][http_www.cnblogs.com_bitzhuwei_p_Longest-Palindromic-Substring-Part-II.html]

[Link 1]: http://en.wikipedia.org/wiki/Longest_palindromic_substring
[o_longestPalindromicSubString01.png]: /images/20220514/0e7dd580cd0e40158280434ca842fe55.png
[o_longestPalindromicSubString02.png]: /images/20220514/8bef23eea4df4a97af341f10126cda29.png
[o_longestPalindromicSubString03.png]: /images/20220514/bafcad5327d647f6a9cca01514e99b6b.png
[o_longestPalindromicSubString04.png]: /images/20220514/66ab894357254d6a9978badab41957af.png
[http_www.cnblogs.com_bitzhuwei_p_Longest-Palindromic-Substring-Part-II.html]: http://www.cnblogs.com/bitzhuwei/p/Longest-Palindromic-Substring-Part-II.html