UVALive - 4975_Casting Spells

题意很简单，给你一个字符串，要求你求出一个最长的形似于w(wr)w(wr)的最长连续子串的长度。wr表示w的逆序串。

在这里大家很容易就能想到Manacher算法求回文串。没有错，就是这个。

算法的详细过程我就不说了，直接说后面的实现吧。

通过manacher算法我们可以在O(N)的时间复杂度以内求出一每两个字符空缺处为对称轴的最长回文串的长度。

这样我们可以对于每一个空缺位置逐一枚举，然后分别对匹配求出一个最长的回文串就可以了。

中间有好多细节要优化哦，我wa了好几发。还有在写的时候一定要写出各种优化。代码不要写挫了。

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #define maxn 1000100

 using namespace std;

 char tep[maxn],s[*maxn];

 int a[*maxn],n,ans,now;

 void init()

 {

     now=;

     s[]='@';

     s[]='#';

     for (int i=; tep[i]; i++)

     {

         s[now++]=tep[i];

         s[now++]='#';

     }

     s[now]='$';

     s[now+]=;

 }

 void deal()

 {

     memset(a,,sizeof a);

     int mx_c=,mx_r=;

     a[]=;

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

     {

         if (mx_r>i)

         {

             a[i]=min(mx_r-i+,a[*mx_c-i]);

         }

         else a[i]=;

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

         if (i+a[i]>mx_r) mx_r=i+a[i]-,mx_c=i;

     }

 }

 int main()

 {

     int cas;

     scanf("%d",&cas);

     while (cas--)

     {

         scanf("%s",tep);

         for (int i=; tep[i]; i++)

             if (tep[i]>='A' && tep[i]<='Z')

                 tep[i]=tep[i]-'A'+'a';

         ans=;

         init();

         deal();

         for (int i=; s[i]; i+=)//这里一定是+2，只有空缺处才是满足条件的。

         {

             int cur=a[i]-;

             while (cur%!= || cur/>=i) cur--;

             for (; cur>ans; cur-=)

             {

                 if (a[i+cur/]>=cur/+ && a[i-cur/]>=cur/+)

                 {

                     ans=cur;

                     break;

                 }

             }

         }

         printf("%d\n",ans);

     }

     return ;

 }

巴特西

UVALive - 4975_Casting Spells

最新文章

热门文章