题意
题目描述
如果一个字符串正着读和倒着读是一样的，则称它是回文的。
给定一个长度为 N 的字符串 S，求他的最长回文子串的长度是多少。
输入格式
输入将包含最多 30 个测试用例，每个测试用例占一行，以最多 106 个小写字符的形式给出。
一个以字符串
END（不包括引号）开头的行表示输入终止。输出格式
对于输入中的每个测试用例，输出测试用例编号和最大回文子串的长度（参考样例格式）。每个输出占一行。
样例
样例输入
abcbabcbabcba abacacbaaaab END样例输出
Case 1: 13 Case 2: 6
题解
回文串还是经常遇见的一种题，所以第一时间想到：答案满足单调性所以二分长度，check函数里O(N)判断是否有长度为 mid 的回文串
有几个需要注意的点（我一开始没想到的）：
- 回文串要分奇回文和偶回文讨论
- 存下反串和原串是对称的，写check的时候要注意一下
代码
回文子串
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f,N = 1e6+10,mod = 1e9+7,base = 233;
ll mi[N<<1],sum[N<<1];
int len,cnt;
char s[N<<1];
void init()
{
mi[0]=1;
for(int i=1;i<=len<<1;i++)
{
sum[i]=sum[i-1]*base+s[i]-'a'+1,sum[i]%=mod;
mi[i]=mi[i-1]*base,mi[i]%=mod;
}
}
inline ll Hash(int l,int r)
{
return (sum[r]-sum[l-1]*mi[r-l+1]%mod+mod)%mod;
}
inline bool check1(int mid)
{
for(int i=mid+1;i+mid<=len;i++)
if(Hash(i-mid,i+mid)==Hash(len*2-(i+mid)+1,len*2-(i-mid)+1))
{
//printf("[%d,%d]==[%d,%d]
",i-mid,i+mid,len*2-(i+mid)+1,len*2-(i-mid)+1);
return true;
}
return false;
}
inline bool check2(int mid)
{
for(int i=mid;i+mid<=len;i++)
if(Hash(i-mid+1,i+mid)==Hash(len*2-(i+mid)+1,len*2-(i-mid+1)+1))
{
//printf("[%d,%d]==[%d,%d]
",i-mid,i+mid,len*2-(i+mid)+1,len*2-(i-mid)+1);
return true;
}
return false;
}
int main()
{
while(1)
{
cnt++;
scanf("%s",s+1);
if(s[1]=='E'&&s[2]=='N'&&s[3]=='D') break;
len=strlen(s+1);
for(int i=1;i<=len;i++) s[i+len]=s[len-i+1];//在S末尾把反串存下来
init();
int l=0,r=len,ans1=0,ans2=0;
while(l<r)//奇回文
{
int mid=(l+r+1)>>1;
if(check1(mid)) l=mid;
else r=mid-1;
}
ans1=(l<<1)+1;
l=0,r=len;
while(l<r)//偶回文
{
int mid=(l+r+1)>>1;
if(check2(mid)) l=mid;
else r=mid-1;
}
ans2=(l<<1);
printf("Case %d: %d
",cnt,max(ans1,ans2));
}
return 0;
}