马拉车回文算法

回文算法"/>

马拉车回文算法

算法原理

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

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

r代表以s_new[id]为中心的最长回文最右边界，也就r=i+p[i]。
 假设我们现在求p[i]，也就是以s_new[i]为中心的最长回文半径，如果i<r，那么： id -i其实就是等于 j ，p[j]表示以s_new[j]为中心的最长回文半径，因为 i 和 j 关于 id 对称，我们利用p[j]来加快查找。（我们已经求出p[pos]）

#include<iostream>
#include<cstring>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1000050;
char a[maxn];
char s[2*maxn];//新字符串和p数组的大小要比原来字符串长度大2倍多； 
int p[2*maxn];
int into()
{int len=strlen(a)//先获取原来字符串的长度 s[0]='@';//新字符串开通设一个特殊符号，防止越界 s[1]='#';//然后每个字符要都夹着 # int j=2;for(int i=0;i<len;i++){s[j++]=a[i];//构造新字符串 s[j++]='#';}s[j]='\0';//末尾设上'\0' return j;//返回新字符串的长度 } 
int manacher()
{int len=into();//接受新字符串的长度 int pos=0,r=0,ans=0;//pos为中心，r为右边界 ，ans为保存的答案 for(int i=1;i<len;i++){if(i<r){//注意要 i<r 时，保证r-i不为负数 p[i]=min(p[2*pos-i],r-i);//利用 2*pos-i==j,	快速确保取最小的正确回文长度 }else p[i]=1;//不符合，则最少回文长度就是自身 while(s[i+p[i]]==s[i-p[i]]){不需边界判断，因为左有'$',右有'\0'  ,只要字符串左右发展相等则另p[i]++ p[i]++;//p[i]表示以s[i]为中心的最长回文的半径 }if(i+p[i]>r){//我们每走一步i，都要和 r 比较，我们希望 r 尽可能的远，这样才能更有机会执行if (i < r)这句代码，从而提高效率 r=i+p[i];//先更新最远右边界 r pos=i;//并且更新pos=i； }ans=max(ans,p[i]-1);//每次更新最长的长度，p[i]-1正好是原文字符串a的回文长度 }return ans;//返回最长的长度 
}
int main()
{int t = 0;while (scanf("%s", a)){t++;memset(p, 0, sizeof(p));//每次计算先清空数组p里面的数 if (a[0] == 'E'&&a[1] == 'N'&&a[2] == 'D')break;printf("Case %d: %d\n", t, manacher());}return 0;}