Manacher HDOJ 5371 Hotaru's problem-白红宇

Manacher HDOJ 5371 Hotaru's problem

阅读量：7246 次

发布时间：2019-06-29

本文共 1823 字，大约阅读时间需要 6 分钟。

1 /* 2     题意：求形如(2 3 4) (4 3 2) (2 3 4)的最长长度，即两个重叠一半的回文串 3     Manacher：比赛看到这题还以为套个模板就行了，因为BC上有道，自己又学过Manacher算法，结果入坑WA到死 4         开始写的是判断是否 p[i]-1 <= p[i+p[i]-1]-1，但是没有想到这种情况：5 (5 1) (1 5) (5 1) 1 5         单靠最长回文半径是不行的，看了网上的解题报告知道，要从极端位置往回挪才行 6         给我的教训是只会套模板是没用的，要灵活的使用该算法。另外max() 函数似乎很费时间 7 　　 8 */ 9 /************************************************10 * Author        :Running_Time11 * Created Time  :2015-8-11 12:52:4912 * File Name     :C.cpp13  ************************************************/14 15 #include 
     
      16 #include 
      
       17 #include 
       
        18 #include 
        
         19 #include 
         
          20 #include 
          
           21 #include 
           
            22 #include 
            
             23 #include 
             
              24 #include 
              
               25 #include 
               
                26 #include 
                
                 27 #include 
                 28 #include 
                  
                   29 #include 
                   
                    30 #include 
                    
                     31 #include 
                     
                      32 using namespace std;33 34 #define lson l, mid, rt << 135 #define rson mid + 1, r, rt << 1 | 136 typedef long long ll;37 const int MAXN = 1e5 + 10;38 const int INF = 0x3f3f3f3f;39 const ll INFF = 0x7fffffff;40 const int MOD = 1e9 + 7;41 int a[MAXN*2], p[MAXN*2];42 int n;43 44 int Manacher(void) {45 a[n] = INF + 2;46 for (int i=n; i>=0; --i) {47 a[i*2+2] = a[i]; a[i*2+1] = INF;48 }49 a[0] = INF + 1; n = n * 2 + 2;50 int id = 0; p[0] = 1;51 for (int i=2; i
                      
                        i) p[i] = min (p[2*id-i], id + p[id] - i);53 else p[i] = 1;54 while (a[i-p[i]] == a[i+p[i]]) p[i]++;55 if (id + p[id] < i + p[i]) id = i;56 }57 58 int mx = 0;59 for (int i=3; i<=n-2; i+=2) {60 if (p[i] - 1 > mx) {61 int c = p[i] - 1;62 while (c > mx && p[i+c] < c) c--;63 mx = mx > c ? mx : c;64 }65 }66 67 return mx / 2 * 3;68 }69 70 int main(void) { //HDOJ 5371 Hotaru's problem71 int T, cas = 0; scanf ("%d", &T);72 while (T--) {73 scanf ("%d", &n);74 for (int i=0; i