Manacher算法介绍

今天做到了一个运用Manacher算法数组性质解决的题目(HYSBZ - 2342)，感觉Manacher算法有点遗忘，所以又重新看了一遍，顺便整理一下。后面再附上这个题的题解。

Manacher算法

在介绍算法之前，首先介绍一下什么是回文串，所谓回文串，简单来说就是正着读和反着读都是一样的字符串，比如abba，noon等等，一个字符串的最长回文子串即为这个字符串的子串中，是回文串的最长的那个。

计算字符串的最长回文字串最简单的算法就是枚举该字符串的每一个子串，并且判断这个子串是否为回文串，这个算法的时间复杂度为O(n^3)的，显然无法令人满意，稍微优化的一个算法是枚举回文串的中点，这里要分为两种情况，一种是回文串长度是奇数的情况，另一种是回文串长度是偶数的情况，枚举中点再判断是否是回文串，这样能把算法的时间复杂度降为O(n^2)，但是当n比较大的时候仍然无法令人满意，Manacher算法可以在线性时间复杂度内求出一个字符串的最长回文字串，达到了理论上的下界。

1.Manacher算法原理与实现

下面介绍Manacher算法的原理与步骤。

首先，Manacher算法提供了一种巧妙地办法，将长度为奇数的回文串和长度为偶数的回文串一起考虑，具体做法是，在原字符串的每个相邻两个字符中间插入一个分隔符，同时在首尾也要添加一个分隔符，分隔符的要求是不在原串中出现，一般情况下可以用#号。下面举一个例子：

（1）Len数组简介与性质 

Manacher算法用一个辅助数组Len[i]表示以字符T[i]为中心的最长回文字串的最右字符到T[i]的长度，比如以T[i]为中心的最长回文字串是T[l,r],那么Len[i]=r-i+1。

对于上面的例子，可以得出Len[i]数组为:

Len数组有一个性质，那就是Len[i]-1就是该回文子串在原字符串S中的长度，至于证明，首先在转换得到的字符串T中，所有的回文字串的长度都为奇数，那么对于以T[i]为中心的最长回文字串，其长度就为2*Len[i]-1,经过观察可知，T中所有的回文子串，其中分隔符的数量一定比其他字符的数量多1，也就是有Len[i]个分隔符，剩下Len[i]-1个字符来自原字符串，所以该回文串在原字符串中的长度就为Len[i]-1。

有了这个性质，那么原问题就转化为求所有的Len[i]。下面介绍如何在线性时间复杂度内求出所有的Len。

（2）Len数组的计算

首先从左往右依次计算Len[i]，当计算Len[i]时，Len[j](0<=j<i)已经计算完毕。设P为之前计算中最长回文子串的右端点的最大值，并且设取得这个最大值的位置为po，分两种情况：

第一种情况：i<=P

那么找到i相对于po的对称位置，设为j，那么如果Len[j]<P-i，如下图：

那么说明以j为中心的回文串一定在以po为中心的回文串的内部，且j和i关于位置po对称，由回文串的定义可知，一个回文串反过来还是一个回文串，所以以i为中心的回文串的长度至少和以j为中心的回文串一样，即Len[i]>=Len[j]。因为Len[j]<P-i,所以说i+Len[j]<P。由对称性可知Len[i]=Len[j]。

如果Len[j]>=P-i,由对称性，说明以i为中心的回文串可能会延伸到P之外，而大于P的部分我们还没有进行匹配，所以要从P+1位置开始一个一个进行匹配，直到发生失配，从而更新P和对应的po以及Len[i]。

第二种情况: i>P

如果i比P还要大，说明对于中点为i的回文串还一点都没有匹配，这个时候，就只能老老实实地一个一个匹配了，匹配完成后要更新P的位置和对应的po以及Len[i]。

 

2.时间复杂度分析

Manacher算法的时间复杂度分析和Z算法类似，因为算法只有遇到还没有匹配的位置时才进行匹配，已经匹配过的位置不再进行匹配，所以对于T字符串中的每一个位置，只进行一次匹配，所以Manacher算法的总体时间复杂度为O(n)，其中n为T字符串的长度，由于T的长度事实上是S的两倍，所以时间复杂度依然是线性的。

下面是算法的实现，注意，为了避免更新Mp的时候导致越界，我们在字符串s的前增加一个特殊字符，比如说‘*’。
 

const int INF=5e5+5;
char s[INF];//原字符串
char Ma[2*INF];//转换后的字符串 
int Mp[2*INF];//Mp[i]表示以i为中心的回文串的半径 
void Manacher()
{
	int l=0;//转换后的字符串长度
	//转换字符串 
	Ma[l++]='*';
	Ma[l++]='#';
	for(int i=0;i<n;i++)
	{
		Ma[l++]=s[i];
		Ma[l++]='#';
	}
	//Manacher算法过程 
	int id=0,mx=0,ans=0;
	//mx即为当前计算回文串最右边字符的最大值
	for(int i=0;i<l;i++)
	{
		Mp[i]=mx>i?min(Mp[2*id-i],mx-i):1;
		while(Ma[i-Mp[i]]==Ma[i+Mp[i]])Mp[i]++;
		if(mx<Mp[i]+i){
			mx=Mp[i]+i;
			id=i;
		}
		ans=max(ans,Mp[i]); 
	}
	//返回Len[i]中的最大值-1即为原串的最长回文子串的长度 
	return ans-1;
}

 

HYSBZ - 2342

题目链接：https://vjudge.net/problem/HYSBZ-2342

                                                             双倍回文

Input

输入分为两行，第一行为一个整数，表示字符串的长度，第二行有个连续的小写的英文字符，表示字符串的内容。

 

Output

输出文件只有一行，即：输入数据中字符串的最长双倍回文子串的长度，如果双倍回文子串不存在，则输出0。

Sample Input

16

ggabaabaabaaball

Sample Output

12

Hint

 

N<=500000

 

思路：利用Manacher数组的含义

附上代码

 

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int n;
const int INF=5e5+5;
char Ma[2*INF];
int Mp[2*INF],l;
char s[INF];
void Manacher()
{
	l=0;
	Ma[l++]='*';
	Ma[l++]='#';
	for(int i=0;i<n;i++)
	{
		Ma[l++]=s[i];
		Ma[l++]='#';
	}
	int id=0,mx=0;
	for(int i=0;i<l;i++)
	{
		Mp[i]=mx>i?min(Mp[2*id-i],mx-i):1;
		while(Ma[i-Mp[i]]==Ma[i+Mp[i]])Mp[i]++;
		if(mx<Mp[i]+i){
			mx=Mp[i]+i;
			id=i;
		}
	}
}
int main()
{
    scanf("%d",&n);
	scanf("%s",s);
	Manacher();
	int ans,j,k;
	int sum=0;	
	for(int i=1;i<l;i+=2){//所求的串一定是偶数，所以只枚举'#'的点 
		ans=Mp[i]-1;
		while(ans>=4)
		{   
		    if(ans<=sum)break;//剪枝，比当前答案小，直接跳出 
			if(ans%4==0)
			{ 
				j=i-ans;//串的左端点 
				k=(j+i)/2;//左串的中心点 
				//若是左边的串能覆盖到i，保证左边的串也为回文串。
				//左右对称，处理一边即可 
				if(k+Mp[k]-1>=i){ 
					sum=max(sum,ans);
				} 
			}
			ans-=2;
		}
	}
	printf("%d",sum);
	return 0;
}