线性求最大回文串匹配算法。

以往我是不太爱学算法的，尤其是这种适用面很狭窄的算法，因为总感觉算法这东西学了也不一定考，考了也不一定能A。不过最近刷题的时候发现，自己经常遇到的一些题，虽然和我学过的算法没什么关系，但是代码技巧和思维技巧，明明就是我学XX算法的时候的思路嘛。再加上我最近的代码能力有所增强，看新算法、学新算法的时间我感觉明显缩短，理解力up↑up↑。于是开始喜欢看新算法了。

据说这个算法赛场上很难有机会用到，因为适用面狭窄。

关于最大回文串的匹配，常见的算法有两种： 1. 用$O(n^2)$的时间复杂度，暴力枚举每一个子串。再对于每一个子串，用$O(n)$的复杂度去判断他是否是一个回文串。总时间复杂度为$O(n^3)$。 2. 用$O(n)$的时间复杂度去枚举中轴，对于每一个中轴，用$O(n)$的时间复杂度去向两边扩展。总时间复杂度为$O(n^2)$。(注意，这种方法对于偶数中轴和奇数中轴会有一些不一样的情况需要考虑。)

Manacher（马拉车）算法

这种算法可以看做是上面第二种算法的一个改进(成电视频中认为这是一个剪枝)。对于第二种算法，如果当前匹配GG了，那么下一次匹配，依然要从$1$(或$0$)开始重新去检查回文串。

然而，回文串里面有大量相似和冗余的信息，我们希望能用回文串本身的一些性质和所包含的信息，去避免每次都要从头开始匹配的问题。

首先，我们需要对串本身进行一些改进，以避免第二种算法对于奇数和偶数需要分开判断的情况。我们在串的每个字母前后都加入特殊字符#，如对于aaa来说，改变后串为#a#a#a。

接下来我们约定四个变量表示：

Ma[i] // Ma表示改进后串，Ma[i]表示第i个字符
Mp[i] // 表示从第i个字符开始向两边延伸，最多可以延伸Mp[i]位（他们都是回文串）。
Mx // 表示之前延伸过的所有回文串，所到达过的最右端。
Id // 表示Mx所对应的回文串的中心。

首先我们初始化：$Mx = 0 , Id = 0 $ 接下来我们和第二种算法所做的基本一样，枚举中轴：

1 2	// 为缩减代码，这里使用strlen函数，实际使用中请务必注意。 for( int i = 0 ; i < strlen(Ma) ; i++ )

分类讨论

情况1 Mx > i

那么如果我们枚举中发现$Mx > i$，便可以说明，之前肯定有某一个串，曾经更新覆盖过$i$，我们能否利用对称的性质，使$i$能有一个比较大的初始值，然后再进行常规操作。

由$Mx > i$ ，我们可以知道显然有$Mx > i > id$，那么既然$Mx$和$Mx'$对称，中轴$id$知道，那么$i$和$i'$也一定会对称。 这是这个算法的核心。 $i'$的坐标是多少呢？就是$2 * id - i$ 由 $id - ( i - id )$得到。

情况(1) i和i'都在Mx与Mx'内

那么我们是不是可以直接使用 $Mp[i] = Mp[ 2 * id - i ]$呢？在$i$和$i'$都在$Mx$和$Mx'$内时，这是正确无误的。

但是还有另外一种情况。

情况(2) i'在Mx'外

当$i'$很长，延伸到了$Mx'$外时，我们并不能保证$i$也能一如既往的延伸到$Mx$以外。这时候我们只能保证$i$在$Mx$以内的时候，是对称的。所以这时候 \[Mp[i] = Mx - i\]

情况(1)和情况(2)

我们并不关心具体是什么情况，因为这对时间复杂度没有影响。所以我们只要Mp[i] = min( Mp[2*id-i] , Mx - i ) 就足够了。

情况2 Mx <= i

遇到这种情况我们怎么办呢？老老实实的去扩展吧。但是在这里我们可以一边扩展，一边去更新Mp[i]的值。

1	while( Ma[ i + Mp[i] ] == Ma[ i - Mp[i] ] ) Mp[i]++;

这样即就是一遍扩展，一遍更新了。

Manacher完整实现

最后，我们把上面这几部分组合一下，并注意更新$Mx$和$Id$的值，就可以了。

code

for( int i = 0 ; i < size ; i++)
{
    if( Mx > i )
    {
        Mp[i] = min( Mp[ 2 * Id - i ] , Mx - i ) ;
    }
    else
        Mp[i] = 1 ;
    while( Ma[i + Mp[i] ] == Ma[i - Mp[i]] )
        Mp[i]++;
    if( i + Mp[i] > Mx )
    {
        Mx = i + Mp[i] ;
        Id = i ;
    }
    ans = max( ans , Mp[i] ) ;
}

最终第i个字符的回文串长度为$Mp[i] - 1$ ## 时间复杂度

这个时间复杂度不是特别好算，我们可以使用摊还分析。具体可以参考一下其他量化分析文章，会很详细。简单的理解可以是：发现$Mx$每次最少往右移动$1$，并且除此之外其他的不会对复杂度有贡献。

遇到的一些问题

理解为何$Mp$数组只是记录了向其中一边延伸的问题，却可以做最终答案：因为#号的存在，使得两边的#号必然相等，那么，一边就可以看做是两边了。
需要正确理解为什么第i个字符的回文串长度需要$-1$：同样因为#的存在，当以#为中心，需要去除中心的#，当以非#为中心，需要去除相邻的一个#。
边界等问题。(有些地方会把开头加一些其他的特殊字符以避免边界问题。目前这类问题我还没有遇到)

参考资料

电子科技大学-字符串算法选讲 (昨天很多博客没看清楚，看了这个半个小时就会了)
有什么浅显易懂的Manacher Algorithm详解 - 知乎 (和第一个一起使用）
O(n)回文子串(Manacher)算法
如何证明Manacher算法的时间复杂度是O(n)