Manacher 算法【马拉车算法详解】最长回文子串

前提：

在了解马拉车算法前，首先你得知道中心扩散法，中心扩散法的意思就是枚举每一个字符，假设以其为中心然后向两边扩散，对于每一个字符我们都会计算出一个他能扩散的最大半径，当然这里面要有奇偶中心的考虑。

最长回文子串【暴力、动态规划、中心扩散、马拉车算法】（LeetCode 5）

中心扩散法的时间复杂度最坏是O(n^2)。例如字符串是"aaaaaaa"，每个字符都会往两边扩散很久。 假如回文串的答案长度很短，是2，形如"abccdefgh"，那么意味着每个字符往两边扩散的时候，很早就会结束，速度会快很多。 所以综上我们可以得出，让中心扩散法变慢的主要原因是那些可以一直扩散的情况。而马拉车算法的作用就是可以通过已知的扩散而快速求出之后的扩散情况。

 

奇偶中心问题：

写过中心扩散法都知道，枚举字符时，不能确定是奇中心还是偶中心，所以我们往往两种情况都要判断下。

马拉车算法为了统一奇偶中心问题，在原字符串里加入原字符串不存在的字符当做间隔符得到一个新字符串。

如图所示，假如我们求出了新字符串的答案，那么原字符串的答案显然就是（新字符串答案-1）/ 2。

至此，我们解决了奇偶中心问题，也解决了新字符串和原字符串之间的答转换，现在我们要去思考如何求出新字符串的答案了。

 

p数组：

马拉车算法的核心思想就是在对一个字符进行中心扩散的时候，先看看能不能利用已知的条件，让扩散的过程快一些。

为了记录已知的扩散，我们用p数组存储每一个字符能扩散的最大半径（不包括他本身）。

如下图所示：

 

维护变量：

枚举的过程，我们需要维护几个特殊的变量。

center：表示当前的回文中心 maxRight：当前能走到的最右边 mirror：当前循环变量i关于center的对称点

 

分情况讨论：

情况一：当 i >= maxRight ，说明对于当前枚举的 i ，是没有前车之鉴可循的，只能老老实实中心扩散。

情况二：当 i < maxRight ，具体要看 p[mirror] 和 maxRight - i 的大小关系决定 p[i] 。 因为 i < maxRight ，说明 i 这个位置在我们之前的计算中是考虑过的，不然maxRight不可能到达这里，所以我们可以借助前面的经验的，来实现快速计算p[i]。

1. 当p[mirror] < maxRight - i , 则 p[i] = p[mirror] 。

maxRight - i 大于 p[mirror]，说明对于 i 这个位置的计算，我们完全可以由center的对称关系得到，因为 i 的扩散逃不出 center 的控制范围。

2. 当p[mirror] == maxRight - i , 则 p[i] = p[mirror] ，然后再中心扩散。

相等说明恰好到达了边界，p[mirror]的值我们还是可以利用的，但是这可能不是最终答案，因为 i 再扩散就超出了maxRight 的范围，之前是没有涉及的，所以我们在继承了 p[mirror] 后应该再尝试着中心扩撒。

可能会扩散到更远的地方，如图

3. 当p[mirror] > maxRight - i , 则 p[i] = maxRight - i 。

由center的对称性可得，maxRight右边的蓝色与对称点左边的黑色是一定不相等的。

所以对称的部分只能到达 maxRight - i 。

总结：

代码：

class Solution { public: //扩展函数，传入扩展的起始点，返回扩展长度 int expand(const string& s, int l, int r) { int ans=0; while (l>= 0 && r<s.size() && s[l]==s[r]) { l--; r++; ans++; } return ans; } string longestPalindrome(string s) { //给字符串加间隔符 string t="#"; for (int i=0; i<s.size(); i++){ t+=s[i]; t+="#"; } s=t; int p[2005]={0}; int center=0; int maxRight=0; int mirror=0; for (int i=0; i<s.size(); i++){ if (i>=maxRight){ //情况一 p[i]=expand(s,i-1,i+1); center=i; maxRight=i+p[i]; }else{ //情况二 mirror=2*center-i; if (p[mirror]<maxRight-i) p[i]=p[mirror]; //小于 else if (p[mirror]>maxRight-i) p[i]=maxRight-i; //大于 else { //等于 p[i]=p[mirror]+expand(s,i-p[mirror]-1,i+p[mirror]+1); center=i; maxRight=i+p[i]; } } } //找答案 int ans=0; int f=0; for (int i=0; i<s.size(); i++){ if (p[i]>ans) ans=p[i],f=i; } //输出答案 string ss=""; for (int i=f-ans; i<=f+ans; i++){ if (s[i]!='#') ss+=s[i]; } return ss; } };

另一种写法：

对于 i < maxRight 第二种情况

可以进行合并，变成：p [ i ] = min ( p [ mirror] , maxRight - i ) ，再尝试中心扩散。

代码：

class Solution { public: //扩展函数，传入扩展的起始点，返回扩展长度 int expand(const string& s, int l, int r) { int ans=0; while (l>= 0 && r<s.size() && s[l]==s[r]) { l--; r++; ans++; } return ans; } string longestPalindrome(string s) { //给字符串加间隔符 string t="#"; for (int i=0; i<s.size(); i++){ t+=s[i]; t+="#"; } s=t; int p[2005]={0}; int center=0; int maxRight=0; int mirror=0; for (int i=0; i<s.size(); i++){ if (i>=maxRight){ //情况一 p[i]=expand(s,i-1,i+1); center=i; maxRight=i+p[i]; }else{ //情况二 mirror=2*center-i; p[i]=min(p[mirror],maxRight-i); p[i]+=expand(s,i-p[i]-1,i+p[i]+1); center=i; maxRight=i+p[i]; } } //找答案 int ans=0; int f=0; for (int i=0; i<s.size(); i++){ if (p[i]>ans) ans=p[i],f=i; } //输出答案 string ss=""; for (int i=f-ans; i<=f+ans; i++){ if (s[i]!='#') ss+=s[i]; } return ss; } };

马拉车算法总结：

马拉车算法用p数组存储了前面计算得出的最大扩展长度，对于一个新的要计算的位置，我们不再直接暴力扩展，而是先查询，在p[mirror]和maxRight-i中选取最小的，再尝试扩展，这样就避免了重复的计算。

马拉车算法是典型的用空间换取时间的算法。

时间复杂度：O(n) 空间复杂度：O(n)