Manacher算法

概述

利用 O(N)的复杂度求出字符串的最大回文半径

前置知识与预处理

回文中心

对于长度为奇数的回文串而言，其具有回文中心，但如果回文串的长度为偶数，那么其无回文中心。
为了处理方便处理，先将字符串拓展成 2length+3 的长度，在首尾补上两个特殊字符当作终止符，编号 1 至 2length+1 之间奇数编号赋值#，偶数编号从小到大依次赋值为原字符串的字符

图例
A B C C C B A
^ # A # B # C # C # B # A # $

显然，处理后的字符串最大回文半径比原字符串大 1

代码逻辑

如果两个元素处于一个回文区间的对称位置，那么可以用前面的元素的最大回文半径给后面元素的最大回文半径赋值，但是赋值时不能让后面元素的最大回文区间右端点超出当下回文区间的右端点，因为可赋值的性质是在当下回文区间之中的性质，超出当下回文区间之后不具备此条由回文区间带来的性质。

利用最大回文半径的赋值，可以复用比较结果，以此优化时间复杂度

代码实现

从前向后遍历结点，只要当下结点还没有抵达或者超越当下回文区间边界，就可以尝试用其对称结点的最大回文半径赋值。
只要当下回文区间不能包含住结点的回文区间，那么当下的回文区间已经不可能再为当下结点已经后续结点提供回文半径赋值的性质，所以将当下回文区间转移为当下结点的回文区间。

1
2
3
4
5
6
7
8
9
10
11
12
int Center = 0, Right = 0;
for(int i=1;i<=2*lenth+1;i++)
{
	if(i<Right) //由于0号为特殊元素不可能加入回文区间，回文左端点最左为1，i<Right时，2*Center-i必然大于0，数组不会越界
		r[i] = r[2*Center-i] < Right-i ? r[2*Center-i] : Right-i;
	else
		r[i] = 1;
	while(s[i+r[i]]==s[i-r[i]])
		r[i]++;
	if(i+r[i]>Right)
		Center = i, Right = i + r[i];
}