由于回文分为偶回文（比如 bccb）和奇回文（比如 bcacb），而在处理奇偶问题上会比较繁琐，所以这里我们使用一个技巧，在字符间插入一个字符（前提这个字符未出现在串里）。举个例子：s="abbahopxpo"，转换为s_new="$#a#b#b#a#h#o#p#x#p#o#"（这里的字符 $ 只是为了防止越界，下面代码会有说明），如此，s 里起初有一个偶回文abba和一个奇回文opxpo，被转换为#a#b#b#a#和#o#p#x#p#o#，长度都转换成了奇数。

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

i	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
s_new[i]	$	#	a	#	b	#	b	#	a	#	h	#	o	#	p	#	x	#	p	#
p[i]		1	2	1	4	5	2	1	2	1	2	1	2	1	2	1	6	1	2	1

可以看出，p[i]-1正好是原字符串中最长回文串的长度。

  Manacher 算法之所以快，就快在对 p 数组的求法上有个捷径，看下图：

  设置两个变量，mx 和 id 。

  mx 代表以s_new[id]为中心的最长回文最右边界，也就是mx=id+p[id]。

  假设我们现在求p[i]，也就是以s_new[i]为中心的最长回文半径，如果i<mx，如上图，那么：

 

if (i < mx)              p[i] = min(p[2 * id - i], mx - i);

2 * id -i其实就是等于 j ，p[j]表示以s_new[j]为中心的最长回文半径，见上图，因为 i 和 j 关于 id 对称，我们利用p[j]来加快查找。

代码：

#include
     
        #include
      
       #include
       
          using namespace std;char s[1000];char s_new[2000];int p[2000];int Init(){    int len = strlen(s);    s_new[0] = '$';    s_new[1] = '#';    int j = 2;    for (int i = 0; i < len; i++)    {        s_new[j++] = s[i];        s_new[j++] = '#';    }    s_new[j] = '\0';  //别忘了哦      return j;  //返回s_new的长度  }int Manacher(){    int len = Init();  //取得新字符串长度并完成向s_new的转换      int maxLen = -1;   //最长回文长度      int id;    int mx = 0;    for (int i = 1; i < len; i++)    {        if (i < mx)            p[i] = min(p[2 * id - i], mx - i);  //需搞清楚上面那张图含义, mx和2*id-i的含义        else            p[i] = 1;        while (s_new[i - p[i]] == s_new[i + p[i]])  //不需边界判断，因为左有'$',右有'\0'              p[i]++;        //我们每走一步i，都要和mx比较，我们希望mx尽可能的远，这样才能更有机会执行if (i < mx)这句代码，从而提高效率         if (mx < i + p[i])          {            id = i;            mx = i + p[i];        }        maxLen = max(maxLen, p[i] - 1);    }    return maxLen;}int main(){    while (printf("请输入字符串：\n"))    {        scanf("%s", s);        printf("最长回文长度为 %d\n\n", Manacher());    }    return 0;}