UVALive 6439--Pasti Pas!

因为它要求的是最长的回文串,我们一方面从前往后走,一方面从后往前走,当某次得到一个相同的部分就看成一个整体,这样就可以得到最长的一个回文串.然后的问题就是如果判断我们枚举的前后两个部分的字符串是否是一样的,我们当然可以暴力判定,但是这样肯定回超时,所以我们采用字符串hash的方法进行判断.

代码如下:

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

typedef  unsigned long long ull;

ull Hash[50500];
char str[50500];

int main()
{
      //freopen("in.txt","r",stdin);
      Hash[0]=1;
      for(int i=1;i<=50500;i++)
           Hash[i]=Hash[i-1]*31;
      int t,Case=0;
      scanf("%d",&t);
      while(t--)
      {
            scanf("%s",str);
            int l=0,r=strlen(str)-1;
            int ans=0,len=0;
            ull x=0,y=0;
            while(1)
            {
                  if(l==r)
                  {
                      ans++; break;
                  }
                  if(l>r)
                  {
                      if(x||y)
                           ans++;
                     break;
                  }
                  if(x==0&&y==0&&str[l]==str[r])
                  {
                        ans+=2;
                        l++;r--; len=0;
                        continue;
                  }
                  x=x*31+(str[l]-‘A‘);
                  y+=Hash[len]*(str[r]-‘A‘);
                  len++;
                  if(x==y)
                  {
                       ans+=2;
                       x=0,y=0,len=0;
                  }
                  l++; r--;
            }
            printf("Case #%d: %d\n",++Case,ans);
      }
   return 0;
}