POJ 3974  

网上看到的O(n)的方法，Manacher算法，记录一下

1 #include 
     
       2 #include 
      
        3 #include 
       
         4  5 #define MAX(a,b) (a>b?a:b) 6 #define MIN(a,b) (a
        
          i)42                 p[i] = MIN(p[2*id-i], mx-i);43             else44                 p[i] = 1;45 46             for(;str[i+p[i]] == str[i-p[i]]; p[i]++) ;47             if(p[i] + i > mx)48             {49                 mx = p[i] + i;50                 id = i;51                 max = MAX(max,p[i]);52             }53             54         }55         printf("Case %d: %d\n", count++, max-1);56     }57 58     return 0;59 }