Hdu 5371 Hotaru's problem (manacher+枚举)

题目链接：

题目描述：

　　给出一个字符串N，要求找出一条N的最长连续子串。这个子串要满足：1：可以平均分成三段，2：第一段和第三段相等，3：第一段和第二段回文。

解题思路：
　　其实通俗来讲就是求符合题意的最长回文串。先用manacher与处理一下字符串N，得出以n[i]与n[i+1]为中心的回文串长度半径记为p[i]，然后循环枚举i作为第一段的终点，p[i]+i-1作为第二段的终点记做j。当p[i]>=(j-i+1)&&p[j]>=(j-i+1)时，这个枚举区间[i, j]才算合法，然后比较求出最大区间长度即可。

 #include <queue>

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int maxn = ;

 int a[maxn*], p[maxn*], n;

 void manather ()

 {

     for (int i=n; i>; i--)

     {

         a[i*  ] = a[i];

         a[i*-] = -;

     }

     n = n *  + ;

     a[] = -;

     a[n] = -;

     int x = ;

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

     {

         if (p[x]+x > i)

             p[i] = min (p[*x-i], p[x]-i+x);

         else

             p[i] = ;

         while (a[i-p[i]] == a[i+p[i]])

             p[i] ++;

         if (x+p[x] < i+p[i])

             x = i;

     }

 }

 int main ()

 {

     int t, l = ;

     scanf ("%d", &t);

     while (t --)

     {

         scanf ("%d", &n);

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

             scanf ("%d", &a[i]);

         manather();

         int ans = ;

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

             for (int j=i+p[i]-; j-i>ans; j-=)

                 if (p[j]>=j-i+ && ans < j-i)

                 {

                     ans = j - i;

                     break;

                 }

         printf ("Case #%d: %d\n", ++l, ans/*);

     }

     return ;

 }

巴特西

Hdu 5371 Hotaru's problem (manacher+枚举)

最新文章

热门文章