题意

给出一个只由小写英文字符a,b,c…y,z组成的字符串S,求S中最长回文串的长度.
回文就是正反读都是一样的字符串,如aba, abba等

思路

用特殊字符插入到s串中每两个字符中间，实现每个回文串都是奇数，再用manacher算法进行求解。

代码

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          using namespace std; const int N = 110009; char s[N], t[N<<1]; int p[N<<1]; int manacher(int len) { int id = 1, mx=0; p[0] = 1; for(int i=1; i
         
           i) p[i] = min(mx-i, p[2*id-i]); else p[i] = 1; while(t[i+p[i]] == t[i-p[i]]) p[i]++; if(mx < p[i]+i) { mx = p[i]+i; id = i; } } int ans = p[1]; for(int i=1; i