如果一个字符串正着读和倒着读是一样的,则称它是回文的。
给定一个长度为N的字符串S,求他的最长回文子串的长度是多少。
输入格式
输入将包含最多30个测试用例,每个测试用例占一行,以最多1000000个小写字符的形式给出。
输入以一个以字符串“END”(不包括引号)开头的行表示输入终止。
输出格式
对于输入中的每个测试用例,输出测试用例编号和最大回文子串的长度(参考样例格式)。
每个输出占一行。
输入样例:
abcbabcbabcba
abacacbaaaab
END
输出样例:
Case 1: 13
Case 2: 6
#include <iostream>
#include <string.h>
using namespace std;
const int N=2000010,base=131;
//根据分析原理我们要将字符串的长度扩大2倍
//并且哈希经验值取131
typedef unsigned long long ULL;
ULL hl[N],hr[N],p[N];
//分别存储正序、逆序、和131进制的数量级
char str[N];//存储源数据
ULL get(ULL h[], int l, int r)
{
return h[r] - h[l - 1] * p[r - l + 1];
}
int main()
{
ios::sync_with_stdio(false);
int T=1;
while(cin>>(str+1),strcmp(str+1,"END"))
{
int n=strlen(str+1);
n*=2;
for(int i=n;i;i-=2)//将源数据进行扩展填充字符
{
str[i]=str[i/2];
str[i-1]='z'+1;
}
p[0]=1;
for(int i=1,j=n;i<=n;i++,j--)
{//分别对源数据进行正序和逆序的哈希值计算和131进制的数量级计算
hl[i]=hl[i-1]*base+str[i]-'a'+1;
hr[i]=hr[i-1]*base+str[j]-'a'+1;
p[i]=p[i-1]*base;
}
//通过把每个位置作为对称点的中心点来进行二分遍历半径
int res=0;
for(int i=1;i<=n;i++)
{
int l=0,r=min(i-1,n-i);//l、r为假设的当前位置对称半径的最小以及最大值
while(l<r)
{
int mid=l+r+1>>1;//这里二分前加1,是因为我们下面有l=mid防止死循环
//下面以半径为mid来半段对称字符串是否相同
if(get(hl,i-mid,i-1)!=get(hr,n-(i+mid)+1,n-i))r=mid-1;
else l=mid;
}
if(str[i-l]<='z')res=max(res,l+1);
else res=max(res,l);
}
printf("Case %d: %d\n",T++,res);
}
return 0;
}
本文地址:https://blog.csdn.net/qq_42635159/article/details/107572120
如对本文有疑问, 点击进行留言回复!!
mysql中如何实现 row_number分组求topN的功能
SQLSERVER中RANK OVER(PARTITION BY)的用法
Kaspersky Endpoint Security 10 for Windows version 10.2.6.3733 is no longer supported
网友评论