POJ 3974-Palindrome(Manacher算法) - c++编程基础

?
题意：求最长的回文串。
思路：同样是用Mancher算法在O(n)的时间内解决(我其实是来练练板子的

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include
              #pragma comment(linker, /STACK:102400000,102400000) using namespace std; typedef long long LL; const int inf=0x3f3f3f3f; const double pi= acos(-1.0); const double esp=1e-6; const int maxn=1000010; char str[maxn]; char s[maxn*2]; int p[maxn*2]; int len; void Manacher() { int i; s[0]='$'; s[1]='#'; for(i=0;i
              





               i) p[i]=min(p[2*id-i],p[id]+id-i); else p[i]=1; while(s[i+p[i]]==s[i-p[i]]) p[i]++; if(p[i]+i>p[id]+id) { id=i; } if(p[i]>MaxL) MaxL=p[i]; } printf(%d ,MaxL-1); } int main() { int icase=1; while(~scanf(%s,&str)) { if(strcmp(str,END)==0) break; len=strlen(str); printf(Case %d: ,icase++); Manacher(); } return 0; }