最长回文
给出只由小写的英文字母a、b、c…y、z构成的字符串s，求出s中最长的回文字符串的长度。
所谓回文，是正反都相同的字符串，例如aba、abba等
输入
在120组以下输入多组case，各组逐行输入由小写的英文字母a、b、c…y、z组成的字符串s
两组case之间由空行分隔。 不处理此空行)
字符串长度len=110000
Output
每行都有一个与一系列case相对应的整数x，它表示该系列case字符串中的最长回文长度。
样品输入
AAAA abab样本输出
43分析：
什么是yxdmj车算法：
据官方介绍，manacher(yxdmj车)算法是寻找字符串的最长回文子串的线性算法。
我的理解是，从字符串的开头到末尾，找出现在右边界最大的回文列部分列，记录对称中心id和右边界mx，利用对称性，给下一个以I为对称中心的回文部分列赋予初始值p[i]以减少时间，然后以I为对称中心，p[i]
字符串的重构：
因为回文串被分成奇数回文串和偶回文串，所以为了避免这样的差异，用与空白字符不同的字符，例如#a#b#a#、#a#b#a#，分隔第一个字符串，重构的回文串都是奇数回文串，进行重构
int l=0，I； a[l ]='$ '； //将字符串从1改为a[l ]='# '； //重新配置数组，使其全部为奇数列for (I=0； ilen； I () a(l )=s (I )； a[l ]='# '； }a[l]=0； //末尾的核心代码的讲解：
用p[i]排列表示以I为回文中心时的最长回文串的半径
从重构字符串的开头开始扫描，首先找到当前右边界最大的回文列部分列，记录对称中心id和右边界mx。 假设左边界为mn，则接下来的I (此时I在id的右边)，一个以id为对称中心，I的对称点j=2*id-i， i p[j]mx，即j的另一个是以i p[j]mx，即j为中心的最大回文列的左边界小于mn的情况，此时，再利用以id为中心的最大回文列的对称性，只能得到I到mx之间的区间然后，根据以上的初始值，判断a[i p[i]]和a[i-p[i]是否相等，如果相等，则判断为p[i]，直到知道不相等为止，最后更新id和mx即可。
int mx=0，id=0； for(I=0； il； I ) if(imx ) p ) I )=min ) p )2*id-I )、mx-i )； //2*id-i是以id为对称中心I对称点elsep[i]=1； //因为半径是a[i]本身，所以1while(a[Ip[i]==a[I-p[I]] ) /原本将p[I]扩展到两侧的if(Ip[I]MX ) {mx=i p[i] ) //mx为以id为中心的最长回文子串的右边界id=i； }完整代码如下：
# include ' stdio.h ' # include ' string.h ' # include ' algorithm ' usingnamespacestd； char a[200010]，s[100010]； int p[200010]； //p[i]是以I为回文中心时最长回文串的半径voidmanacher(intlen ) ) {int l=0，I； a[l ]='$ '； //将字符串从1改为a[l ]='# '； //重新配置数组，使其全部为奇数列for (I=0； ilen； I () a(l )=s (I )； a[l ]='# '； }a[l]=0； //清除末尾的int mx=0、id=0； for(I=0； il； I ) if(imx ) p ) I )=min ) p )2*id-I )、mx-i )； //2*id-i是以id为对称中心I对称点elsep[i]=1； //因为半径是a[i]本身，所以1while(a[Ip[i]==a[I-p[I]] ) /原本将p[I]扩展到两侧的if(Ip[I]MX ) {mx=i p[i] ) //mx为以id为中心的最长回文子串的右边界id=i； }}}int main () ) while(~scanf('%s”，s ) ) intlen=strlen )，I； manacher(len )； int ans=0； for(I=0； i2*len 2； I ) )//顺序扫描以查找最长的半径。 半径减去1，等于原始字符串中回文字符串的总长度ans=max(ans，p[i]-1 )。 printf(%d(n )，ans )； }return 0； }