HDU3068-manacher算法-最长回文串

https://vjudge.net/problem/HDU-3068

求最长的回文串。

有一次用dp求过一次。

：我们都知道求回文串可以依赖于暴力的方法（以某点为重心，暴力的比呗），manacher方法的思想在于利用对称性来减少暴力运算，从而提高效率。

从左到右遍历字符，记录最大的 回文串的右界（记当时的 字符位置为i）

分两种情况 1 当前遍历字符x在 右界右边。这时候无法利用对称性，只能一个一个算了。qwq 对应图第一个

2 单前字符 在字符右界左边，hiahia 这下就可以利用了qwq

① x以i对称的点的 回文串 完全被包括在 最大回文串中，由于对称性说明当前的点的 回文串也被完全包括，无法拓展（如果可以拓展的话，那么左边也可以拓展，但是左边已经计算过了，所以不能拓展） ，对应图第二个 为 dp[id*2-i]（id*2-i意思就是id对称的i的位置）

② x以i对称的点 的回文串 的左界 小于 最长回文串的左界（更左），这时候的长度 为 dp[id]+id-i(根据对称性计算) ,为 绿色靠左那一部分。

③ 对称点的左界和最大左界相等， 这时候可能 会增加。

具体见代码

#include <bits/stdc++.h>
using namespace std;
/* manacher
  求最长回文串，暴力操作。
 就是利用对称性，来减少这种操作。
  记录 最长的能够到达的位置。
  同时定义了三种情况。
    不愿意看到的情况  ，暴力查找。
   2 愿意看到的情况
   分三种情况 
*/
int main()
{   char  s[];
    int p[*+];
    char b[*+];
    while(~scanf("%s",s)){
         //下面，是构造‘我们需要的串’的过程
         memset(p,,sizeof(p));
         b[]='*';
         int t=;
         int len=strlen(s);
         for(int i=;i<len;i++){
             b[t++]='#';
             b[t++]=s[i];
         }
         b[t]='#';
         int zz=,rig_max=;
         int max1=;
         for(int i=;i<t;i++){
             if(zz+p[zz]>i) //包含在里面了
              {  p[i]=min(p[zz*-i],p[zz]-i+zz);
                 while(b[i+p[i]]==b[i-p[i]])
                    p[i]++;//延伸
              }
              else{
                 p[i]=;
                 int j=;
                 while((i>=j)&&b[i+j]==b[i-j])
                      p[i]++,j++;
              }
              if(p[i]+i>p[zz]+zz){
                  zz=i;
              }
              if(p[i]>max1) max1=p[i];
         }
         printf("%d\n",max1-);
    }
    return ;
}