HDU 5371 Hotaru's problem （Manacher，回文串）

时间：2021-09-20 15:05:28

　　

题意：给一个序列，找出1个连续子序列，将其平分成前，中，后等长的3段子序列，要求【前】和【中】是回文，【中】和【后】是回文。求3段最长为多少？由于平分的关系，所以答案应该是3的倍数。

思路：先Manacher求最长子串，利用期间所记录的P 数组，穷举一下所有可能的前两串，再用O(1)时间判断第3串是否符合要求。

　　具体做法：

　　（1）P[i]记录的是以i为中心，从i-P[i]+1到i+P[i]-1这段都是回文。由于前两段之和必为偶数，所以必须选取str[i]为'#'的。

　　（2）扫一遍每个'#'，以其最长的回文开始穷举（仅需将P[i]--即可，然后找到右边对应的'#'，判断P[i]是不是大于所穷举的长度），直到3段都满足要求了，跳出此‘#’，换下一个。

　　

 #include <iostream>

 #include <cstring>

 #include <vector>

 #include <stdio.h>

 using namespace std;

 const int N=;

 int n;

 int s[N*];

 int P[N*];

 int cal(int len)

 {

     if(n<) return ;

     memset(P,,sizeof(P));

     int id=, mx=;

     P[]=;

     P[]=;

     for(int i=; i<len; i++)

     {

         P[i] =i>mx? : min( P[*id-i], mx-i);

         while(s[i+P[i]]==s[i-P[i]])    P[i]++;

         if(i+P[i]>mx)

         {

             id=i;

             mx=i+P[i];

         }

     }

     int ans=;

     for(int i=; i+<len; i+=)

     {

         int tag=P[i]-;

         if( tag> && tag>ans )

         {

             while( P[i+tag]<=tag && tag>ans )    tag--;

             if(tag>ans) ans=tag;

         }

     }

     return ans/*;

 }

 int main()

 {

     //freopen("input.txt", "r", stdin);

     int t, tmp, j=;

     cin>>t;

     while(t--)

     {

         scanf("%d", &n);

         s[]=-;

         s[]=-;

         for(int i=,j=; i<n; i++)

         {

             scanf("%d",&tmp);

             s[j++]=tmp;

             s[j++]=-;

         }

         s[n*+]=-;

         printf("Case #%d: %d\n", ++j, cal( n*+ ));

     }

     return ;

 }

AC代码

相关文章