manacher学习笔记

啊，做题的时候突然发现自己忘了这个东西，遂填坑。
manacher算法，俗称“马拉车”算法。
此算法得名于发明人。。。（马拉车大佬）
此算法的作用：在$O(n)$的复杂度下解决回文子串问题。
先来看一个问题：

给出一个字符串，求出其最长的回文子串。

Part 1: naive

我们先看暴力做法：
暴力枚举子串。。。然后判断，复杂度是$O(n^3)$。
还有一种算法如下：以一个位置为中心，尝试向左、右拓展，当左边和右边的字符相等时继续前进，直到到达边界或者不相等为止。
然后，由于长度为偶数的回文串，其中心在两个字符中间，所以我们对原串进行改造：在每个字符之间插入同一种字符。
大致效果如下：
abacaba->a#b#a#c#a#b#a
然后执行上述算法，大致代码如下，其中$len_x$表示以x为中心最长的拓展长度。

int len[N];
char a[N];//此处假定原串已按照上述方式改造
void deal(){
	for(int i=0;i<=m;i++){
		len[i]=1;
		while(i+len[i]-1<=m&&i-len[i]+1>=0&&a[i+len[i]-1]==a[i-len[i]+1])
			len[i]++;
		len[i]--;
	}
}

由于每个字符间都插入了一个额外的字符，所以这个算法算出来的$len\_x$，虽然是一个方向的拓展长度，但它代表的，就是它整个串的长度。
此算法的复杂度，明显比$O(n^3)$要优秀，它的复杂度是$O(n^2)$。

Part 2:优化

manacher算法，就是在上面$O(n^2)$的算法基础上，进行优化，使复杂度变为$O(n)$.
它的主要优化在于：利用之前得到的回文串计算结果，来减少比对次数。
为实现此算法，我们额外维护两个数值：
$MaxRight$:之前发现的回文串中，右端延伸到的位置最远的那个串延伸到的位置。
$pos$:这个回文串的中心所在位置。
然后，在枚举中心的位置基础上，我们通过一些分析，来定义$len_x$的初值。
这就是manacher的具体原理，在上面那个框架的基础上，加入对$len_x$的初值定义，减少计算次数。

Part 3:分类讨论

考虑以下情况：

当前位置，在$MaxRight$左侧：

在此情况下，i位置是包含在以pos为中心的回文串中的，我们定义其关于pos的对称点为j。

$len_j+i-1\leq MaxRight$

这种情况如此图所示：

绿色部分是j为中心的回文串，而i,j是对称的，所以i为中心的这个与j的回文串对称的子串，也是一个回文串。因此，我们可以直接令$len_i=len_j$。

$len_j+i-1\gt MaxRight$

这种情况如此图所示：

由于红串内才保证是回文的，所以，虽然橘色很长，甚至延伸到了外面，但是我们只能取其“在红串中”的回文部分。所以，我们取绿色部分（即$len_i=MaxRight-i$）

当前位置，在$MaxRight$右侧：

这个时候，由于其不在回文串中，所以我们必须从头开始进行比较过程，也就是$len_i=1$。

分类讨论之后，就还是按照上述方法，进行拓展。
拓展结束之后，别忘了更新MaxRight和pos

复杂度证明

还是按照上述情况分析：

此情况下，其实不会有任何拓展。。。
因为如果能拓展，在处理j的时候就做到了。。。

此情况下，等于直接从MaxRight处开始向外拓展，拓展一次，MaxRight就会增加一次。

另外的情况下，相当于把pos移动到当前的i，同时也一定会增加MaxRight。
综上，每次操作，要么增加MaxRight，要么增加pos，两者都小于字符串长度，所以复杂度为$O(n)$。

实现

代码如下~

int len[N],MaxRight=-1,pos=0;
char a[N];//此处假定原串已按照上述方式改造
void deal(){
	for(int i=0;i<=m;i++){
		if(i<MaxRight){
			len[i]=min(len[2*pos-i],MaxRight-i);//刚好对应上述情况
		}else len[i]=1;
		
		while(i+len[i]-1<=m&&i-len[i]+1>=0&&a[i+len[i]-1]==a[i-len[i]+1])
			len[i]++;
		len[i]--;
		if(i+len[i]-1>MaxRight){
			MaxRight=i+len[i]-1;
			pos=i;
		}//千万别忘了更新MaxRight
	}
}