manacher 算法

序言

manacher 好像有点不熟练了，怕翻车了，写篇文章理理思路。

---

目标

给定一个字符串 $S$S，以 $O(n)$O(n) 的复杂度，求出以每一个点为中心的最长的回文子串的长度。

预处理

首先对于字符串如 abaccaa，将其两两字符之间插入一个#，并在首尾各插入一个不常用的字符（避免边界问题），如变为?#a#b#a#c#c#a#a#$，这样的一个新串在处理时就无需考虑长度为偶数的回文子串，如回文子串 acca 在新串中对应的 #a#c#c#a#，且新串中回文子串的半长恰为原来的两倍。

暴力

对于每一个字符，暴力枚举比对以其为中心的最长回文子串的长度，$O(n^2)$O(n2)。

---

manacher

manacher 利用回文串的性质，通过对不同情况的讨论处理，完成对回文子串的 $O(n)$O(n) 求解。

回文串性质

给一个回文串 $S$S，如 cabaemeabac，我们发现这个的左半边包含了一个回文子串aba，那么其右半边对称的位置也一定有这样一个回文子串aba，反之亦然。

形式化：$S=\{a_1a_2...a_{n-1}a_n\}$S={a1​a2​...an−1​an​} 是回文串，$\exist i \le j，i \neq n-j + 1，\{a_ia_{i+1}...a_{j-1}a_j\}$∃i≤j，i̸​=n−j+1，{ai​ai+1​...aj−1​aj​} 是回文子串，那么 $\{a_{n-j+1}a_{n-j+2}...a_{n-i}a_{n-i+1}\}${an−j+1​an−j+2​...an−i​an−i+1​} 也一定是回文子串。

同样的如果不是回文子串，那么对称的位置也一定不为回文子串。

三个标记和一个数组：

P：Position，当前字符所在位置；
R：Right，当前最靠右的最长回文子串的右端点所在位置；
C：Center，当前最靠右的最长回文子串的中心所在位置；
r[i]：表示以第 $i$i 个字符为中心的最长回文子串长度半长，所以 $i+r[i]$i+r[i] 即为以第 $i$i 个字符为中心的最长回文子串的右端点所在位置。

分类讨论：

1. $P > R$P>R，$r[P]=1$r[P]=1；
2. $P \le R$P≤R，找到 $P$P 关于 $C$C 的对称位置 $D$D，$D =C-(P-C)=2C-P$D=C−(P−C)=2C−P：
   2.1. $P+r[D] \le R$P+r[D]≤R，根据性质，$r[P] = r[D]$r[P]=r[D]；
   2.2. $P+r[D] > R$P+r[D]>R，根据性质，$r[P] = R-P$r[P]=R−P（认真看一下性质）。

对于 $1$1 和 $2.2$2.2 （$2.1$2.1 如果暴力找显然直接结束）都还可以以 $P$P 为中心寻找更长的回文子串（暴力查找），然后更新 $C$C 和 $R$R。

复杂度分析

复杂度的瓶颈显然在于暴力查找匹配最长回文子串的过程。

每次暴力查找都是从 $R$R 的位置开始找，且每次找完都一定会向右更新 $R$R，所以暴力查找次数等于 $R$R 的最大值，因为 $R \le |S|$R≤∣S∣，暴力查找最多进行 $|S|$∣S∣ 次，所以复杂度为 $O(n)$O(n)。

---

代码

void Manacher()
{
	int C = 1, R = 1;
	r[1] = 1;
	for(int P = 1; P <= n; ++P)
	{
		r[i] = min(R - P + 1, r[C * 2 - P]); //讨论了1,2.1和2.2
		while(S[P - r[P]] == S[P + r[P]]) ++r[P]; //暴力判断回文子串
		if(R < P + r[i] - 1){ R = P + r[P] - 1; C = P; } //更新C和P
	}
}