1089 最长回文子串 V2（Manacher算法） 
基准时间限制：1 秒 空间限制：131072 KB 分值: 0  难度：基础题
题目链接
 收藏
 关注
回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。
输入一个字符串Str，输出Str里最长回文子串的长度。
Input 
输入Str（Str的长度 <= 100000)
Output 
输出最长回文子串的长度L。
Input示例 
daabaac
Output示例 
5

题解：字符串的Manacher算法。

Manacher算法：

    1.先预处理字符串（注意两点：第一个处理的不同，另外末尾也要有#）

    S  #  1  #  2  #  2  #  1  #  2  #  3  #  2  #  1  #
    P  1  2  1  2  5  2  1  4  1  2  1  6  1  2  1  2  1

    (p.s. 可以看出，P[i]-1正好是原字符串中回文串的总长度）

    2.在一个大的回文串中，若有一个小的回文串，可以直接找到另一个小的回文串。

    参考博客：

1.打开链接

2.打开链接

注意：

1.之前一直超时，最后发现原因是，用for(int i=0;i<strlen(a);i++)这样会超时的，因为每次都计算了一次a串的长度，时间复杂度很高。

#include<bits/stdc++.h>
using namespace std;
char b[110000*2],a[110000*2];
int j=1,r=0,id=0,p[110000*2],max1=0;
int main()
{
	scanf("%s",a);
	b[0]='@';
	for(int i=0;a[i]!='\0';i++)
	{
		b[j++]='#';
		b[j++]=a[i];
	}
	b[j]='#';
	for(int i=0;b[i]!='\0';i++)
	{
		if(i<r)
		{
			p[i]=min(p[2*id-i],r-i);
		}
		while(b[p[i]+i]==b[i-p[i]]) p[i]++;
		if(p[i]+i>r)
		{
			r=p[i]+i;
			id=i;
		}
		if(p[i]>max1)
		{
			max1=p[i];
		}
	}
	printf("%d\n",max1-1);
	return 0;
}