Manacher's Algorithm

Manacher's

马拉车算法其实就是用来解决最长回文字符串的问题的。

回文串就是正反读起来就是一样的，如“abba”。

如果暴力去解决这个问题的话，它的时间复杂度是O(n^3) 当然我们还可以优化一下采用中心检测法，这样可以使算法的复杂度降为O(n^2) + O(1)

现在重点来了，马拉车算法可以将该问题的复杂度降到O(N)

马拉车算法：

一）第一步是改造字符串S，变为T，其改造的方法如下：(为什么要改造呢？主要是为了统一奇数和偶数的情况)

在字符串S的字符之间和S的首尾都插入一个“#”，如：S=“abba”变为T="#a#b#b#a#" 。我们会发现S的长度是4，而T的长度为9，长度变为奇数了！！那S的长度为奇数的情况时，变化后的长度还是奇数吗？我们举个例子，S=“abcba”，变化为T=“#a#b#c#b#a#”，T的长度为11，所以我们发现其改造的目的是将字符串的长度变为奇数，这样就可以统一的处理奇偶的情况了。

二）第二步，为了改进回文相互重叠的情况，我们将改造完后的T[ i ] 处的回文半径存储到数组P[ ]中，P[ i ]为新字符串T的T[ i ]处的回文半径，表示以字符T[i]为中心的最长回文字串的最端右字符到T[i]的长度，如以T[ i ]为中心的最长回文子串的为T[ l, r ]，那么P[ i ]=r-i+1。这样最后遍历数组P[ ]，取其中最大值即可。若P[ i ]=1表示该回文串就是T[ i ]本身。举一个简单的例子感受一下：

数组P有一性质，P[ i ]-1就是该回文子串在原字符串S中的长度，那就是P[i]-1就是该回文子串在原字符串S中的长度，至于证明，首先在转换得到的字符串T中，所有的回文字串的长度都为奇数，那么对于以T[i]为中心的最长回文字串，其长度就为2*P[i]-1,经过观察可知，T中所有的回文子串，其中分隔符的数量一定比其他字符的数量多1，也就是有P[i]个分隔符，剩下P[i]-1个字符来自原字符串，所以该回文串在原字符串中的长度就为P[i]-1。

另外，由于第一个和最后一个字符都是#号，且也需要搜索回文，为了防止越界，我们还需要在首尾再加上非#号字符，实际操作时我们只需给开头加上个非#号字符，结尾不用加的原因是字符串的结尾标识为''，等于默认加过了。这样原问题就转化成如何求数组P[ ]的问题了。（因此我们可以在字符串的首加上‘¥’）

三）如何求数组P [ ]

求解数组P[ ]其实就是根据前 P[i-1] 从而推导出 P[i] 从而避免许多重复的匹配（这有点像KMP算法）

从左往右计算数组P[ ]， Mi为之前取得最大回文串的中心位置，而R是最大回文串能到达的最右端的值。

1）当 i <=R时，如何计算 P[ i ]的值了？毫无疑问的是数组P中点 i 之前点对应的值都已经计算出来了。利用回文串的特性，我们找到点 i 关于 Mi 的对称点 j ，其值为 j= 2*Mi-i 。因，点 j 、i 在以Mi 为中心的最大回文串的范围内（[L ,R]），

a）那么如果P[j] <R-i （同样是L和j 之间的距离），说明，以点 j 为中心的回文串没有超出范围[L ,R]，由回文串的特性可知，从左右两端向Mi遍历，两端对应的字符都是相等的。所以P[ j ]=P[ i ]（这里得先从点j转到点i 的情况），如下图：

b)如果P[ j ]>=R-i （即 j 为中心的回文串的最左端超过 L），如下图所示。即，以点 j为中心的最大回文串的范围已经超出了范围[L ,R] ，这种情况，等式P[ j ]=P[ i ]还成立吗？显然不总是成立的！因，以点 j 为中心的回文串的最左端超过L，那么在[ L, j ]之间的字符肯定能在( j, Mi ]找到相等的，由回文串的特性可知，P[ i ] 至少等于R- i，至于是否大于R-i（图中红色的部分），我们还要从R+1开始一一的匹配，直达失配为止，从而更新R和对应的Mi以及P[ i ]。

2）当 i > R时，如下图。这种情况，没法利用到回文串的特性，只能老老实实的一步步去匹配。

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <stdbool.h>
 5 #include <stdlib.h>
 6 #include <string>
 7 #include <string.h>
 8 #include <math.h>
 9 #include <vector>
10 #include <queue>
11 #include <stack>
12 #include <set>
13 #include <map>
14 
15 #define INF 0x3f3f3f3f
16 #define LL long long
17 #define MAXN 2000005
18 using namespace std;
19 
20 char Ma[MAXN*2];
21 int Mp[MAXN*2];
22 char s[MAXN];
23 
24 void Manacher(char s[],int len)
25 {
26     // 预处理
27     int l = 0;
28     Ma[l++] = '$';
29     Ma[l++] = '#';
30     for (int i=0;i<len;i++)
31     {
32         Ma[l++] = s[i];
33         Ma[l++] = '#';
34     }
35     Ma[l++] = 0;
36     //根据Mp[i-1]递推出Mp[i]
37     int mx = 0;  // i-1的最右端
38     int id = 0;  // i-1的中心
39     for (int i=0;i<l;i++)
40     {
41         Mp[i] = mx>i?min(Mp[2*id-i],mx-i):1;
42         while (Ma[i+Mp[i]] == Ma[i-Mp[i]])
43             Mp[i]++;
44         if (i+Mp[i]>mx)
45         {
46             mx = Mp[i]+i;
47             id = i;
48         }
49     }
50 }
51 
52 int main()
53 {
54     scanf("%s",s);
55     int len = strlen(s);
56     Manacher(s,len);
57     int ans = 0;
58     for (int i=0;i<2*len+2;i++)
59         ans = max(ans,Mp[i]-1);
60     printf("%d
",ans);
61     return 0;
62 }