Manacher

用途：

给一个字符串，求它的最长回文子串；比如：

$\qquad$ s = "abbacbca"，最长回文子串为 "acbca"，长度为 $5$；

如果用暴力的算法，枚举对称轴，向两边延伸；复杂度高达 $O(n^2)$ !

有个叫 Manacher 的人发明了一种算法，可以 $O(n)$ 的求出最长回文子串，就叫 Manacher 算法(俗称 马拉车算法)；

算法详情：

预处理：

回文串分为 奇回文串(如 "acbca") 和 偶回文串(如 "abba")；

处理的时候判奇偶是一件很麻烦的事，所以用一个小技巧对原串进行预处理：

在头尾以及两两字符中间都插入一个无关字符 (没有出现在这个串中的字符)；

举个例子："abcd" 填充之后 变为 "#a#b#c#d#"；只要是无关字符都可以用来填充；

偶回文串 "abba" 处理后变为 "#a#b#b#a#"，奇回文串 "acbca" 处理后变为 "#a#c#b#c#a#"，长度都变成了奇数；

p[] 的定义：

首先定义一个 $p$ 数组：

$\quad \bullet$ $p[i]$ 表示以 $i$ 为中心的回文串的最大回文半径。

比如：

i	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
New	@	#	a	#	b	#	b	#	a	#	c	#	b	#	c	#	a	#
p[i]		1	2	1	2	5	2	1	2	1	2	1	6	1	2	1	2	1

求解p[]

假设我们正在求 $p[i]$，即 $p[1, \cdots, i-1]$ 都已求出；

新增两个变量 Mr 和 Mid，定义如下：

• Mr : 中心在 $i​$ 之前的所有回文子串，所能延伸至的最右端的位置；

• Mid : 右端延伸至 Mr 处的回文子串的中心位置；
  即 Mid + p[Mid] = Mr；

假设变量的相对位置如图：

(1) if (i < Mr)
即以 Mid 为中心的回文串为黑色的那段覆盖了红色的两段，

根据回文串的性质，有 以 j 为中心 的回文串 和 以 i 为中心 的回文串相等，即图中红色两段相等；

既然这样，就不用以 $i$ 为中心向两边延伸了，直接 p[i] = p[j] ，加速查找；

(2) else
即 $i$ 在 Mr 右边，这种情况，只能老老实实向两边延伸了；

参考代码：

/**********************************************
 *Author*        :XzzF
 *Created Time*  : 2018/4/12 16:42:30
 *Ended  Time*  : 2018/4/12 16:57:48
*********************************************/

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long LL;
const int inf = 1 << 30;
const LL INF = 1LL << 60;
const int MaxN = 110005;

char s[MaxN + 5];
char New_s[2 * MaxN + 5];  //填充字符之后的串
int p[2 * MaxN + 5];  //p[i]表示以i为中心的最长回文串半径

int Get_New() {
	int len = strlen(s);
	New_s[0] = '@'; New_s[1] = '#';
	int L = 1;
	for(int i = 0; i < len; i++) {
		New_s[++L] = s[i];
		New_s[++L] = '#';
	}
	New_s[L + 1] = '\0';   //不要忘了
	return L;
}

int Manacher() {
	int len = Get_New();
	int Max_len = 0;
	int Mr = 0;       //遍历过的所有回文串中,所能到达的最右端的位置
	int Mid = 0;       //能到达最右端位置的回文串的中心位置
	for(int i = 1; i <= len; i++) {
		if(i < Mr) 
			p[i] = min(p[2 * Mid - i], Mr - i);
		else p[i] = 1;

		//不需边界判断,因为左有'@',右有'\0'
		while(New_s[i - p[i]] == New_s[i + p[i]])
			p[i]++;

		//更新Mr
		if(Mr < i + p[i]) {
			Mid = i;
			Mr = i + p[i];
		}
		Max_len = max(Max_len, p[i] - 1);
	}
	return Max_len;
}

int main()
{
	while(scanf("%s", s) != EOF)
	{
		printf("%d\n", Manacher());
	}
    return 0;
}

算法复杂度分析：

算法复杂度主要来自于那两个循环，外层 for() 循环就不说了，少不了的；主要看里面的 while() 循环进去多少次？ i > Mr 必定会进入 while() 循环，就不看了；

i <= Mr 时的各种情况分析：

当 i <= Mr 时，主要会遇到以下几种情况：

前提条件：那段黑色的表示以 Mid 为中心的回文串；

下文中 “回文串x” 表示 以x为中心 的回文串；

回文串 j 全部在 回文串 Mid 内部：

对于这种情况，在while() 之前会有 p[i] = p[j] ；如果会进入 while() 循环，那么 回文串 i 的半径一定会有增量，假设增量为图中绿色那段；

由回文串的性质可得，a = b = c = d ；那么，目前的 $p[j]$ 就等于 紫线+绿线，与原始 $p[j]$ 的定义矛盾！

所以，这种情况不会进入 while() 循环；

回文串 j 部分在 回文串 Mid 之外：

对于这种情况，在 while() 之前就会有 p[i] = Mr - i；如果会进入 while() 循环，回文串 i 的半径同样会有增量，同样设为图中绿色那段；

同理可得，a = b = c = d ；那么 $p[Mid]$ 就等于 黑线+绿线，同样与原始的 $p[Mid]$ 定义矛盾！

所以，这种情况也不会进入 while() 循环；

回文串 j 的左端正好和 回文串 Mid 的左端重合：

对于这种情况，p[i] = Mr - i 之后，依旧有可能增加，所以会进入 while() 循环；

一本正经的假分析：

首先明确，Mr 是递增的！且当 Mr 等于右边界时，就不会再进入 while() 循环了！

在算法过程中，只要进入 while() 循环，一定会使得 Mr 增加！而且， while() 循环进行多少次 Mr 就会增加多少；

也就是说，在最坏的情况下，Mr 最多增加 $len$ 次，也就等价于内层 while() 循环最多执行 $len$ 次；加上外层循环的 $len$ 次，最坏为 $2 * len$ 次；

其中，$len$ 为填充后的串的长度，即 $len = 2n$，$T_{worst} = O(4n)$ ， 所以，算法复杂度为 $O(n)$ 。

实践出真知：

定义一个变量 cnt ；在外层 for() 循环下面 和 内层 while() 下面各写上一句 cnt++; 最后输出看看 cnt 的值：

s	cnt
aaaaaaaaa	36
ababababa	35
abcdefghi	28
abbacabab	34

还是不错的吧！