相当简单好写，话说这个板子我写了很久了今天懒得再敲直接

1 //马拉车（manacher）算法是求字符串内最大回文子串的算法，时间复杂度为线性 2 #include 
     
       3 #include 
      
        4 #include 
       
         5 #include 
        
          6 #include 
         
           7 #include 
          
            8 #include 
           
             9 #include 
            
             10 #include 
             
              11 #define N (100000+5)12 #define oo 2147483647 13 using namespace std;14 char a[N],f[N<<1];15 int len[N<<1],slen;16 void init(){17 cin>>a;18 slen=strlen(a);19 f[0]='@';20 for(int i=1;i<=2*slen;i+=2){21 f[i]='#';22 f[i+1]=a[i/2];23 }24 f[2*slen+1]='#';25 f[2*slen+2]='$';26 }27 void manacher(){28 int mx=0,id=0,ans=0;29 for(int i=1;i<=2*slen;i++){30 if(mx>i){31 len[i]=min(mx-i,len[2*id-i]);32 }33 else{34 len[i]=1;35 }36 while(f[i+len[i]]==f[i-len[i]]){37 len[i]++;38 }39 if(mx
             
            
           
          
         
        
       
      
     

 

贴上来吧