O(n)的复杂度求回文串：Manacher算法
定义一个回文值，字符串S是K重回文串，当且仅当S是回文串，且其长度为⌊N/2⌋的前缀和长度为⌊N/2⌋的后缀是K−1重回文串
现在给一个2*10^6长度的字符串，求其每个前缀的最大回文值之和。
设dp[i]为长度为i的前缀的最大回文值。
当长度为i的前缀的字符串是回文串的时候，有：dp[i]=dp[i/2]+1
若不是回文串 dp[i]=0
接下来就是怎么样快速的判断回文串了，推荐算法Manacher算法。
Manacher算法先对字符串进行修改 如 aba -> $#a#b#a#
那么该怎么用DP求？
显然一下几点是满足的：
如果某个前缀是回文串，该前缀的末端一定是字符#，（因为第一个符号是#）
故对于不是字符#的位置，它的dp值一定为0
如果最大延伸数组p[i]=i，即向左正好延伸到最左边，那么1~p[i]+i-1一定是一个回文前缀
若第i位是#号 ： dp[mx]=dp[i] 其中mx=p[i]+i-1
对于不是#的情况 ： dp[mx]=dp[i-1] 其中mx=p[i]+i-1
#include<bits/stdc++.h>
#define eps 1e-9
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define MAXN 4000005
#define MAXM 40005
#define INF 0x3fffffff
#define PB push_back
#define MP make_pair
#define X first
#define Y second
#define lc (k<<1)
#define rc ((k<<1)1)
using namespace std;
typedef long long LL;
int i,j,k,n,m,x,y,T,ans,big,cas,num,len;
bool flag; int p[MAXN],dp[MAXN];
char str[MAXN],s[MAXN]; void kp()
{
int i;
int mx = ;
int id;
for(i=n; str[i]!=; i++)//清除n后边多余的部分
str[i] = ; //没有这一句有问题。。就过不了ural1297，比如数据：ababa aba
for(i=; i<n; i++)
{
if( mx > i )
p[i] = min( p[*id-i], p[id]+id-i );
//因为是从左往右扫描的这里i>id, 2*id-i是i关于id的对称点，该对称点在id的左端
//p[id]+id是描述中的mx，即id向右延伸的端点位置
//显然向右延伸是可能超出mx的，所以要有下边的for循环
else
p[i] = ;
for(; str[i+p[i]] == str[i-p[i]]; p[i]++); if( p[i] + i > mx )//更新mx与id，因为mx是向右延伸的最大长度，所以实时更新
{
mx = p[i] + i;
id = i;
}
}
} void init()//处理字符串
{
int i, j, k;
str[] = '$';
str[] = '#';
for(i=; i<n; i++)
{
str[i*+] = s[i];
str[i*+] = '#';
}
n = n*+;
s[n] = ;
} int main()
{
scanf("%s",s);
n=strlen(s);
init();
kp();
for (i=;i<n;i++)
{
if (p[i]==i)
{
int mx=p[i]+i-;
if (str[i]!='#')
{
dp[mx]=max(dp[mx],dp[i-]+);
}else
dp[mx]=max(dp[mx],dp[i]+);
}
}
int sum=;
for (i=;i<n;i++) sum+=dp[i];
printf("%d\n",sum);
return ;
}