abstract：manacher算法的输入是一个字符串，可以计算出以每个字符为中心的最长回文子串的半径。为了避免讨论奇数偶数，将原串的每两个字母之间以及前后各加一个特殊字母，比如'#'，那么对于abcbb就变成了 #a#b#c#b#b#，串的长度变成了11，我们用dp[i]表示以i为中心的最长回文的半径，那么上面的串的dp值如下：# a # b # c # b # b #1 2 1 2
manacher算法的输入是一个字符串，可以计算出以每个字符为中心的最长回文子串的半径。为了避免讨论奇数偶数，将原串的每两个字母之间以及前后各加一个特殊字母，比如'#'，那么对于abcbb就变成了 #a#b#c#b#b#，串的长度变成了11，我们用dp[i]表示以i为中心的最长回文的半径，那么上面的串的dp值如下：
# a # b # c # b # b #
1 2 1 2 1 4 1 2 3 2 1
设串为S,那么S[i-dp[i]+1,i-1]=S[i+1,i+dp[i]-1]。
我们从前向后依次计算每个位置的dp值。设现在计算到了i位置，之前所有位置j的最大的j+dp[j]的位置为id,Max=id+dp[id]。
下面分三种情况（设j=2*id-i,即j为i关于id的对称点）：
(1)Max-i>dp[j]：如下图，这说明以j为中心的回文串完全在以id为中心的回文串的内部，那么由于对称性可得，以i为中心的回文串的半径dp[i]=dp[j]。
(2)Max-i<=dp[j]:如下图，那么以j为中心的回文串超出了以id为中心的回文串，那么绿色方框内的部分必然是对称的，那么dp[i]至少等于Max-i。外面的不能确定，我们可以强行匹配。
(3)Max<=i，我们强行匹配这种情况即可。
代码如下，为了方便，在最开始加入一个特殊字母'$'
void manacher(char *s,int n,char *S,int dp[])
{
int cur=0;
S[cur++]='$';
S[cur++]='#';
for(int i=0;i<n;i++) S[cur++]=s[i],S[cur++]='#';
n=cur;
int Max=0,id=0;
for(int i=1;i<n;i++)
{
dp[i]=Max>i?min(dp[2*id-i],Max-i):1;
while(S[i+dp[i]]==S[i-dp[i]]) dp[i]++;
if(i+dp[i]>Max) Max=i+dp[i],id=i;
}
}