UVALive 6439--Pasti Pas!

UVALive 6439--Pasti Pas!

因為它要求的是最長的回文串,我們一方面從前往後走,一方面從後往前走,當某次得到一個相同的部分就看成一個整體,這樣就可以得到最長的一個回文串.然後的問題就是如果判斷我們枚舉的前後兩個部分的字符串是否是一樣的,我們當然可以暴力判定,但是這樣肯定回超時,所以我們采用字符串hash的方法進行判斷.

代碼如下:

#include
#include
#include
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;
}