Manacher算法

Manacher算法

Manacher能对物体施加“力”……

Manacher是一种字符串匹配算法。此算法的核心在于 \(rds\) 数组以及它的求法。

（Manacher算法与Z算法高度相似，因此本blog高仿Z算法）

\(rds\) 数组

定义 \(rds\) 数组： \(rds_{a,i}\) 表示以字符串 \(a\) 的第 \(i\) 位为中心，最多能往两边各扩展多少，使得覆盖过的是一个回文串，即 \(rds_{a,i}=\max\limits_{a_{i-j+1\sim i+j-1}=a_{i-j+1\sim i+j-1}^\mathrm r}\{j\}\) 。例如若 \(a=\texttt{abacabac}\) ，那么 \(rds_a=[1,2,1,4,1,3,1,1]\) 。

\(rds\) 数组的求法

给定字符串 \(a\) ，现在我们需要求出 \(rds_a\) 。

假设我们现在已经知道了 \(rds_{a,1\sim i-1}\) 和使得覆盖过的回文子串的右端点 \(r=mid+rds_{a,mid}-1\) 最大的回文中心 \(mid\) 和右端点 \(r\) ，要求出 \(rds_{a,i}\) 并更新 \(mid,r\) ，那么分 \(2\) 种情况：

1. \(r<i\) 。此时我们直接从第 \(i\) 位往左右两边暴力匹配求出 \(rds_{a,i}\) 。此时显然 \(i+rds_{a,i}-1>r\) ，于是令 \(mid=i,r=i+rds_{a,i}-1\) ；
2. \(r\geq i\) 。设 \(2mid-i=i'\) ，即 \(i'\) 是 \(i\) 关于 \(mid\) 对称的位置。此时又分 \(2\) 种情况：
   1. \(i+rds_{a,i'}\leq r\) 。此时 \(i+rds_{a,i'}\leq r\Rightarrow -i-rds_{a,i'}\geq-r\Rightarrow i-rds_{a,i'}\geq2i-r\) ，显然 \(i>mid\) ，所以 \(i-rds_{a,i'}>2mid-r\) 。所以 \(\left[i-rds_{a,i'},i+rds_{a,i'}\right]\subsetneq[2mid-r,r]\) 。根据 \(rds\) 的定义， \(a_{2mid-r\sim r}\) 是回文串，所以 \(\forall j\in\left[i-rds_{a,i'},i+rds_{a,i'}\right],a_j=a_{2mid-j}\) ，即 \(a_{i-rds_{a,i'}\sim i+rds_{a,i'}}=a_{2mid-\left(i+rds_{a,i'}\right)\sim 2mid-\left(i-rds_{a,i'}\right)}^\mathrm r=a_{i'-rds_{a,i'}\sim i'+rds_{a,i'}}^\mathrm r\) 。那么以 \(a\) 的第 \(i\) 位为回文中心向两边扩展时的回文情况和以第 \(i'\) 位为回文中心是一样的，直接令 \(rds_{a,i}=rds_{a,i'}\) ， \(mid,r\) 不变；
   2. \(i+rds_{a,i'}>r\) 。同理， \(a_{2i-r\sim r}=a_{2mid-r\sim 2i'-(2mid-r)}^\mathrm r=a_{2mid-r\sim 2mid-2i+r}^\mathrm r\) 。那么 \(a_{2i-r\sim r}\) 与 \(a_{2mid-r\sim 2mid-2i+r}\) 的回文性是相同的，显然 \(rds_{a,i}\) 至少有 \(r-i+1\) 这么多，于是直接左边从第 \(2i-r-1\) 位、右边从第 \(r+1\) 位开始暴力向两边匹配求出 \(rds_{a,i}\) ，并令 \(mid=i,r=i+rds_{a,i}-1\) 。

这样按上述方法从 \(i=1\) 递推到 \(i=|a|\) ，便可求出 \(rds_a\) 数组。

下面是求 \(rds\) 数组的代码：

//|a|=n
void manacher(){
	int mid=0,r=0;//使得右端点最大的回文中心和右端点
	for(int i=1;i<=n;i++)//从i=1递推到i=n
		if(r<i){//第1种情况
			rds[i]=0;
			while(i-rds[i]>=1&&i+rds[i]<=n&&a[i-rds[i]]==a[i+rds[i]])rds[i]++;//直接向两边暴力匹配
			mid=i;r=i+rds[i]-1;//更新右端点最大的回文中心和右端点
		}
		else if(i+rds[2*mid-i]<=r)rds[i]=rds[2*mid-i];//第2种情况的第1种情况
		else{//第2种情况的第2种情况
			rds[i]=r-i+1;//rds[i]至少有r-i+1这么多
			while(i-rds[i]>=1&&i+rds[i]<=n&&a[i-rds[i]]==a[i+rds[i]])rds[i]++;//后面再暴力匹配
			mid=i;r=i+rds[i]-1;//更新右端点最大的回文中心和右端点
		}
}

时间复杂度

按上述方法求 \(rds\) 数组的时间复杂度是线性的 \(\mathrm{O}(|a|)\) 。

证明 （感性） ：观察上述方法可发现，只有当 \(i>r\) 时，才可能将这个位置的字符作为在当前回文中心右边的那个字符与左边关于回文中心对称的字符匹配，而匹配结束后会把 \(r\) 更新至最后一个匹配成功的位置，所以每个字符最多会作为在当前回文中心右边的那个字符与左边关于回文中心对称的字符成功匹配 \(1\) 次，所以匹配成功的总次数为 \(\mathrm{O}(|a|)\) ；算 \(rds_{a,i}\) 时，如果往后暴力匹配（即遇到的不是第 \(2\) 种情况的第 \(1\) 种情况），那么第 \(1\) 次匹配失败就会停下来，所以匹配失败的总次数也为 \(\mathrm{O}(|a|)\) 。因此总时间就是匹配所花的时间 \(\mathrm{O}(|a|)+\mathrm{O}(|a|)=\mathrm O(|a|)\) 再加上一些赋值、更新 \(mid,r\) 等一些 \(1\) 次只要 \(\mathrm O(1)\) 的操作，就还是 \(\mathrm O(|a|)\) 了。得证。

应用

\(rds\) 数组可以通过对每个回文中心二分+哈希共 \(\mathrm O(|a|\log_2|a|)\) 求出。显然，Manacher复杂度更优。

接下来是 \(2\) 个经典的应用：

1. 给定字符串 \(a,|a|=n\) ，求 \(a\) 的最长回文子串。显然，回文子串分成 \(2\) 类：

   1. 长度为奇数。此时回文中心是 \(a\) 的某个字符，此类回文子串的最大长度显然为 \(\max\limits_{i=1}^n\{2rds_{a,i}-1\}\) ；
   2. 长度为偶数。此时回文中心是 \(a\) 中某 \(2\) 个相邻字符之间的间隔。这可怎么办呢？我们可以强行塞一个字符到每个间隔里，即令 \(b=\sum\limits_{i=1}^{n-1}(a_i+\texttt!)+a_n\) ，对它跑Manacher。

   然鹅还是需要调整调整。显然，长度为奇数的回文子串也可以用跟偶数一样的方法算，这样只需要跑一次Manacher。不难发现，当以 \(b\) 的某个字符的位置为回文中心的最长回文子串抵到了 \(b_1\) 或 \(b_{|b|}\) ，那么两端不是 \(\texttt!\) ，否则是 \(\texttt!\) 。 \(2\) 种情况，给将 \(b\) 中回文子串的长度还原成 \(a\) 中所对应的回文子串的长度造成了麻烦。不妨在 \(b\) 两端再加一个 \(\texttt!\) ，即令 \(b=\sum\limits_{i=1}^{n}(\texttt!+a_i)+\texttt!\) ，这样以 \(b\) 的某个字符的位置为回文中心的最长回文子串两端一定是 \(\texttt!\) 了。此时 \(b\) 中的最长回文半径 \(rds_{b,i}\) 所对应的 \(a\) 中的回文子串的长度为 \(rds_{b,i}-1\) ，于是答案为 \(\max_{i=1}^{|b|}\{rds_i-1\}\) ；

2. 给定字符串 \(a,|a|=n\) ，求 \(a\) 的非空回文子串个数。与上面那个问题类似，令 \(b=\sum\limits_{i=1}^{n}(\texttt!+a_i)+\texttt!\) ，那么答案为 \(\sum\limits_{i=1}^{|b|}\left\lfloor\dfrac{rds_{b,i}}2\right\rfloor\) 。