hdu 5371 Hotaru's problem【manacher】-白红宇

hdu 5371 Hotaru's problem【manacher】

阅读量：7165 次

发布时间：2019-06-29

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

题目链接：

pid=5371

题意：

给出一个长度为n的串，要求找出一条最长连续子串。这个子串要满足：1：能够平均分成三段，2：第一段和第三段相等，3：第一段和第二段回文。求最大子串的长度。

代码：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   using namespace std;const int N = 1100550;int n, l, tmp;int p[2 * N];//记录回文半径int str0[N];//原始串int str[2 * N];//转换后的串void init(){ int i; str[0] = -2; str[1] = -1; l = 2; for (i = 0, l = 2; i
                   
                    i) p[i] = p[2 * id - i]>(mx - i) ? (mx - i) : p[2 * id - i]; else p[i] = 1;//假设i>=mx，要从头開始匹配 while (str[i + p[i]] == str[i - p[i]]) p[i]++; if (i + p[i]>mx)//若新计算的回文串右端点位置大于mx。要更新po和mx的值 { mx = i + p[i]; id = i; } } int ans = 0; for (int i = 1; i < l; i += 2) for (int j = i + p[i] - 1; j - i > ans; j -= 2) { if (p[j] >= j-i+1 && ans < j - i) { ans = j - i; break; } } return ans / 2 * 3;}int main(){ int t; int cases = 1; scanf("%d", &t); while (t--) { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d",&str0[i]); init(); printf("Case #%d: %d\n", cases++, solve()); } return 0;}