最长回文子串(Manacher算法----时间复杂度O(n) )

简介

马拉车算法是一种在O(n)时间内求一个字符串的最长回文子串的算法

思路

对于最长回文子串,我们可以有很多朴素算法

1. 比如穷举所有子串,然后验证这些子串是否是回文的,这样的复杂度是O(n^3)
2. 比如我们遍历数组,对于每一个元素,我们都认为其是某个回文子串的中心,我们同时向两边伸展,然后取其中的最大值,这样的算法的复杂度是O(n^2)

马拉车算法就是在方法2的基础上进行了扩展,注意方法2做了大量重复的计算,比如,整个数组就是一个回文串,其包含两个对称的小的回文串,这样就做了很多无用功.马拉车算法就是充分利用了这种性质来减少时间复杂度的.

变量

我们设置以下变量：

id : 当前的最长回文子串的中心点

mx  ：是目前已知的最长回文子串的最右一位的后一位

Len[]  : Len[i]表示以i为中心的最长子串能扩展的最长位置-i+1,即i+Len[i]得到的位置是以i为中心的最长回文子串扩展的最远位置的下一位(此处的设计是为了呼应上文的mx) // Len[]数组的大小应该为原字符串的大小的2倍还多,且Len[0]一定为0

预处理

另外我们还要对字符串进行预处理

因为我们发现回文有两种情况,一种是奇数的,一种是偶数的,偶数的形式是没有中心位置的,这就对后续的计算带来极大的不方便,因此我们进行预处理.

预处理的思路是让所有的回文串都变成奇数形式.我们采用如下的思路

原字符串: ababc

预处理后:$#a#b#a#b#c#

注意文中的$和#应该都为在字符串本体中不会出现的字符

这样处理过后,除去开头的$之外,字符串主体一定是奇数

算法 

对于给定的 i 我们找一个和它关于 id 对称的 j ,也就是 id-j == i-id,换言之就是  j==2*id-i 如果发生这种情况,我们就不难发现, i 和 j 的最长回文子串在 id 的回文串范围内的部分应该是一模一样的,但是在外面的部分就无法保证了,当然,最好的情况是i和j的回文子串范围都很小,这样就保证了他俩的回文子串一定一模一样,对于超出的部分我们也没有办法,只能手动扩展,也就是上文的方法2.

如果 i 大于 mx ,说明我们无法用已知的最长回文子串来优化这个计算,所以只能老老实实用上文的方法2来计算

经过以上的处理我们不要忘记更新 id 和 mx ,同时记录最长的回文子串的长度 maxn (代码中写的是 sum ),最后输出答案即可.

但是! 我们之前进行了预处理,而且 Len[i] 仅仅是一半的数组长度,这个该怎么进行转换才能得到最长回文子串的答案呢?

其实如果不考虑预处理的话,仅仅就预处理后的字符串而言,回文子串长度是 1+2*(Len[i]-1) ,也就是 2*Len[i]-1 ,预处理后的字符串长度(不考虑开头的$),是 2*s.size()+1 ,也就是说两个式子联立,就得到了 2*Len[i]-1 == 2*s.size()+1 解得 s.size()==Len[i]-1

所以最后的答案是 max(Len[i]-1)
 

Problem Description

输入一个字符串Str，输出Str里最长回文子串的长度。

回文串：指aba、abba、cccbccc、aaaa这种左右对称的字符串。

串的子串：一个串的子串指此（字符）串中连续的一部分字符构成的子（字符）串
例如 abc 这个串的子串：空串、a、b、c、ab、ac、bc、abc

 

Input

输入Str（Str的长度 <= 1000)

Output

输出最长回文子串的长度L。

Input Sample

daabaac

Output Sample

5

思路：

Manacher求最长回文子串裸题，Manacher求最长回文串，时间复杂度为O(n).

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#define Max 110005
using namespace std;
char Ma[Max*2];//预处理后的字符串每一位是什么
int Mp[Max*2];//相当于上面提到的len[i]
void Manacher(char s[],int len)
{
	int l=0;
	Ma[l++]='$';
	Ma[l++]='#';
	for(int i=0;i<len;i++){
		Ma[l++]=s[i];
		Ma[l++]='#';
	}
	Ma[l]=0;
	int mx=0,id=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(i+Mp[i]>mx){
			mx=i+Mp[i];
			id=i;
		}
	}
}
char s[Max];
int main()
{
	while(scanf("%s",s)!=EOF){
		int len=strlen(s),ans=0;
		Manacher(s,len);
		for(int i=0;i< 2*len+2;i++){
			ans=max(ans,Mp[i]-1);
		}
		cout<<ans<<endl;
	}
	return 0;
}