// 考试太差了 悲伤
如果一个字符串正着读和倒着读是一样的,则称它是回文的。
给定一个长度为 N 的字符串 S,求他的最长回文子串的长度是多少。
输入格式
输入将包含最多 30 个测试用例,每个测试用例占一行,以最多 1000000 个小写字符的形式给出。
输入以一个以字符串 END 开头的行表示输入终止。
输出格式
对于输入中的每个测试用例,输出测试用例编号和最大回文子串的长度(参考样例格式)。
每个输出占一行。
输入样例:
abcbabcbabcba
abacacbaaaab
END
输出样例:
Case 1: 13
Case 2: 6
include[HTML_REMOVED]
include[HTML_REMOVED]
define ULL unsigned long long
using namespace std;
const int P=1331,N=1000001;
ULL h1[N],h2[N],p[N];
char x[N];
int len,ans,n;
void pre_work()
{
len=strlen(x);
for(int i=1;i<=len;i)
{
h1[i]=h1[i-1]P+(ULL)(x[i-1]-‘a’+1);
h2[i]=h2[i-1]P+(ULL)(x[len-i]-‘a’+1);
}
}
bool uzi(int v)
{
int s=len-v+1;
for(int i=1;i<=s;i)
{
/ for(int j=i;j<i+v;j) printf(“%c”,x[j-1]);
printf(“\n”);/
if(h1[i+v-1]-h1[i-1]p[v]==h2[len-i+1]-h2[len-i-v+1]*p[v]) return true;
}
return false;
}
int main()
{
p[0]=1,n=0;
for(int i=1;i<=1000000;i)
p[i]=p[i-1]P;
while(scanf(“%s”,x)&&x[0]!=’E’)
{
n++;
pre_work();
int i=1,j=len;
while(i<j)
while(i<j)
{
int mid=(i+j)/2+1;
if(uzi(mid)) i=mid;
else if(uzi(mid+1)) i=mid+1;
// else if(uzi(mid-1)) i=mid-1;
else j=mid-1;
// printf(“*%d\n%d %d\n”,mid,i,j);
}
printf(“Case %d: %d\n”,n,i);
}
}
时间复杂度:不及丢
顶
宝宝最棒^ ^
呕
、
顶
顶
54188