hdu 3068 Manacher算法 O（n）回文子串算法

题目：http://acm.hdu.edu.cn/showproblem.php pid=3068

关于算法的教程 推荐这个：http://blog.csdn.net/ggggiqnypgjg/article/details/6645824 注意：我推荐的这篇博客里说的那个代码有bug，我觉得没问题，而是博主在用的时候写错了，博主举得反例我都过了 而且hdu 3068也过了

最开始是用的后缀数组，2000ms+ 果断超时...............

看过一遍很快就学会这个算法了：然后A掉

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #define MAXN 200010 using namespace std; int p[MAXN],n; char str[MAXN],s[MAXN]; void pk() { int mx=0,id; for(int i=n; str[i]!=0; i++) str[i] = 0; for(int i=1;i
         
          i) p[i]=min(p[id*2-i],mx-i);//这里写成min(id*2-i,mx-i)，WA得我快吐了 但是奇怪的是，还能跑328ms else p[i]=1; while(str[i-p[i]] == str[i+p[i]])p[i]++; if(i+p[i]>mx) { mx=p[i]+i; id=i; } } } void init() { int i,j; n=strlen(s); str[0]='$';//标记开头，可以用其他不会在测试样例中出现的字符，同样保证了在算p[i]的时候肯定不会越界，空字符肯定不等于$ str[1]='#';//间隔,可以用其他不会在测试样例中出现的字符 for(i=0,j=2;i