題目連結:http://poj.org/problem?id=3974
題目大意:
多樣例:
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiAzNfRHLGZkRGZkRfJ3bs92YsYTMfVmepNHL4VEROpXTE5EeJpHW4Z0MMBjVtJWd0ckW65UbM5WOHJWa5kHT20ESjBjUIF2X0hXZ0xCMx81dvRWYoNHLrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdssmch1mclRXY39CXldWYtlWPzNXZj9mcw1ycz9WL49zZuBnL0QjM1QzMzcTMxAjNwkTMwIzLc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
每個樣例輸出它的最長回文串。
T<=30, n<=1000000
思路:想用用字元串水一水,以為會T,結果AC了。時間複雜度:O(T* n * log n)
直接枚舉回文中心:二分回文長度。作為奇數回文?還是偶數回文?
用了兩個哈希,一個倒着維護。友善判斷是否相等。
#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
int maxn=1000005;
ull base =131;
char s[1000005];
ull g[2][1000005];
ull p[1000005];
void Hash(char s[])
{
int len=strlen(s);
ull ans=0;
g[0][0]=s[0];
for(int i=1;i<len;i++)
{
g[0][i]=g[0][i-1]*base+s[i];
}
g[1][0]=s[len-1];
int cut=1;
for(int i=len-2;i>=0;i--, cut++)
{
g[1][cut]=g[1][cut-1]*base+s[i];
}
return;
}
void getp()
{
p[0]=1;
for(int i=1;i<=maxn;i++)
{
p[i]=p[i-1]*base;
}
return;
}
ull getLR(int l, int r, int k)//取出T裡l - r裡面的字元串的hash值
{
if(l==0)
{
return g[k][r];
}
return g[k][r]-g[k][l-1]*p[r-l+1];
}
int dfs(int i, int mid, int Len, int k)
{
if(k==0)
return getLR(i-mid, i-1, 0)==getLR(Len-i-mid-1, Len-i-2, 1);
if(k==1)
return getLR(i-mid+1, i, 0)==getLR(Len-i-mid-1, Len-i-2, 1);
}
int main()
{
int T=1;
getp();
while(~scanf("%s",s),s[0]!='E')
{
Hash(s);
int Len=strlen(s), MAX1=0, ID1=0, MAX2=0, ID2=0;
for(int i=1;i<=Len-2;i++)
{
int L=1, R=min(i, Len-i-1), k=0;//奇數
while(L<=R)
{
int mid=(L+R)/2;
if(dfs(i, mid, Len, 0))
{
L=mid+1;k=mid;
}
else
{
R=mid-1;
}
}
if(k>MAX1)
{
MAX1=k, ID1=i;
}
L=1, R=min(Len-i-1, i+1), k=0; //偶數
while(L<=R)
{
int mid=(L+R)/2;
if(dfs(i, mid, Len, 1))
{
L=mid+1;k=mid;
}
else
{
R=mid-1;
}
}
if(k>MAX2)
{
MAX2=k, ID2=i;
}
}
printf("Case %d: %d\n",T++,max(MAX2*2, MAX1*2+1));
/***********************輸出回文串*******************************/
// if(MAX2*2>MAX1*2+1)
// {
// for(int i=ID2-MAX2+1;i<=ID2+MAX2;i++)
// {
// printf("%c",s[i]);
// }
// }
// else
// {
// for(int i=ID1-MAX1;i<=ID1+MAX1;i++)
// {
// printf("%c",s[i]);
// }
// }
// printf("\n");
}
return 0;
}