manacher算法主要是处理字符串中关于回文串的问题的，它可以在 O（n） 的时间处理出以字符串中每一个字符为中心的回文串半径，由于将原字符串处理成两倍长度的新串，在每两个字符之间加入一个特定的特殊字符，因此原本长度为偶数的回文串就成了以中间特殊字符为中心的奇数长度的回文串了。

模板是从 kuangbin 巨巨的模板改过来的。

有注释版：

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5  6 const int maxn=1e6+5; 7 char s[maxn],t[maxn<<1];        //s是原串，t是倍长后的串，p是以某个字符为中心的回文串长度，p[i]-1 就是以 i 字符为中心的回文串在原串中的长度 8 int p[maxn<<1]; 9 10 void manacher(){11     int len=strlen(s),l=0;        //原串从0开始12     t[l++]='$';                    //开头字符是一个特殊字符13     t[l++]='#';                    //倍长串中间的间隔都用这个字符14     for(int i=0;i
        
         i?min(p[2*num-i],maxx-i):1;    //若当前字符小于已经判断过的最远长度，那么就定初始值是 i关于num对称的位置的回文串长度 和 当前位置到最远距离的长度 的最小值，若还没有判断到过，那么就初始为122         while(t[i+p[i]]==t[i-p[i]])p[i]++;        //判断直到不构成回文串23         if(i+p[i]>maxx){                        //判断是否拓展到更远位置24             maxx=i+p[i];25             num=i;26         }27     }28 }
        
       
      
     

 

木有注释版：

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5  6 const int maxn=1e6+5; 7 char s[maxn],t[maxn<<1]; 8 int p[maxn<<1]; 9 10 void manacher(){11     int len=strlen(s),l=0;12     t[l++]='$';13     t[l++]='#';14     for(int i=0;i
        
         i?min(p[2*num-i],maxx-i):1;22         while(t[i+p[i]]==t[i-p[i]])p[i]++;23         if(i+p[i]>maxx){24             maxx=i+p[i];25             num=i;26         }27     }28 }