Manacher最长回文串算法

回文串算法"/>

Manacher最长回文串算法

 Manachar算法主要是处理字符串中关于回文串的问题的，它可以在 O（n） 的时间处理出以字符串中每一个字符为中心的回文串半径，由于将原字符串处理成两倍长度的新串，在每两个字符之间加入一个特定的特殊字符，因此原本长度为偶数的回文串就成了以中间特殊字符为中心的奇数长度的回文串了。       ------摘自百度百科

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

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

一.通常解决的问题

给定一个字符串，求出其最长回文子串。例如：
（1）s="abcd", 最长回文长度为 1；
（2）s="ababa", 最长回文长度为 5；
（3）s="abccb", 最长回文长度为 4，即 bccb。

经典例题：HDU3068

  以上问题的传统思路大概是，遍历每一个字符，以该字符为中点向两边查找。其时间复杂度为 O(n2)，很不高效。而在 1975 年，一个叫 Manacher 的人发明了一个算法，Manacher 算法，也称马拉车算法，该算法可以把时间复杂度提升到 O(n)。下面来看看马拉车算法是如何工作的。

二.算法原理

       奇偶变换：为处理字符串方便，现将给定的任意字符串进行处理，使所有可能的奇数/偶数长度的回文子串都转换成了奇数长度。具体就是在每个字符的两边都插入一个特殊的符号。比如hhjj变成 #h#h#j#j#， aba变成 #a#b#a#；为防止数组越界，可以在字符串的开始加入另一个特殊字符，比如“?#a#b#a#?” 。

定义一个辅助数组int p[]，p[i]表示以s_new[i]为中心的最长回文的半径，例如：

i	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
s_new[i]	$	#	a	#	b	#	b	#	a	#	h	#	o	#	p	#	x	#	p	#
p[i]		1	2	1	4	5	2	1	2	1	2	1	2	1	2	1	6	1	2	1

可以看出，p[i]-1正好是原字符串中最长回文串的长度。
  Manacher 算法之所以快，就快在对 p 数组的求法上有个捷径，看下图：

设置两个变量，mx 和 id 。
  mx 代表以s_new[id]为中心的最长回文最右边界，也就是mx=id+p[id]。
  假设我们现在求p[i]，也就是以s_new[i]为中心的最长回文半径，如果i<mx，如上图，那么：

if (i < mx)p[i] = min(p[2 * id - i], mx - i);

2 * id -i其实就是等于 j ，p[j]表示以s_new[j]为中心的最长回文半径，见上图，因为 i 和 j 关于 id 对称，我们利用p[j]来加快查找。

#include<stdio.h> 
#include<iostream>  
#include<cstring>
#include<algorithm>  
using namespace std;
const int maxn=111111;
char s[maxn];
char s_new[maxn*2];
int p[maxn*2];
int Init(){int len = strlen(s);s_new[0] = '$';s_new[1] = '#';int j = 2;for (int i = 0; i < len; i++){s_new[j++] = s[i];s_new[j++] = '#';}s_new[j] = '\0';  //printf("%s\n",s_new);return j;  //返回s_new的长度  
}
int Manacher(){int len = Init();  //取得新字符串长度并完成向s_new的转换  int maxLen = -1;   //最长回文长度  int id;int mx = 0;for (int i = 1; i < len; i++){if (i < mx)p[i] = min(p[2 * id - i], mx - i);  //需搞清楚上面那张图含义, mx和2*id-i的含义elsep[i] = 1;while (s_new[i - p[i]] == s_new[i + p[i]])  //不需边界判断，因为左有'$',右有'\0'  p[i]++;//我们每走一步i，都要和mx比较，我们希望mx尽可能的远，这样才能更有机会执行if (i < mx)这句代码，从而提高效率 if (mx < i + p[i])  {id = i;mx = i + p[i];}maxLen = max(maxLen, p[i] - 1);// printf("%d %d %d\n",mx,id,maxLen);}/*for(int i=1;i<=len;i++)printf("%d ",p[i]);printf("\n");*/return maxLen;
}
int main(){scanf("%s", s);printf("%d\n", Manacher());return 0;
}