题目右转luogu1210
我看到这道题的第一想法是枚举答案 （长度）
但是很显然会超时，怎样优化枚举是关键
我想到了二分答案。但是二分答案要求答案具有单调性。
乍一看，似乎回文子串没什么单调性。但是如果我们将答案分为奇偶两种，答案的单调性就出来了
1.当最长回文串长度是奇数时：
不妨假设长度为\(9\)，那么我们就会发现，\(9\)以下的奇数长度 （1,3,5,7） 都是存在回文串的，奇数的单调性我们找到了
2.当回文串为偶数时
同理，设长度为\(6\)，\(6\)以下的偶数长度 （2,4） 也都是可以的。
然后我们就可以开始二分了
相信写程序对各位DALAO不是问题，上代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=20005;
string s,t;int len1;
int begin,end;
int ans;
struct node
{
char S;
int start;
}st[maxn];
bool ok(int x,int y)
{
int rt=x,lt=y;
while(rt<=lt)
{
if(st[rt].S!=st[lt].S) return false;
rt++,lt--;
}
return true;
}
bool add(int x)
{
int head=1,tail=x;
while(tail<=len1)
{
if(ok(head,tail))
{
begin=st[head].start;
end=st[tail].start;
return true;
}
head++,tail++;
}
return false;
}
int main()
{
while(getline(cin,t))//注意读入数据的处理
{
s+=t+'\n';
};
s=' '+s;
int len=s.size()-1;
for(int i=1;i<=len;i++)
{
if(s[i]>='A'&&s[i]<='Z') st[++len1].S=s[i]-'A'+'a',st[len1].start=i;//改小写
else if(s[i]>='a'&&s[i]<='z') st[++len1].S=s[i],st[len1].start=i;
}
int lt=0,rt;
if(len1%2==0) rt=len1;
else rt=len1+1;
while(lt+2<rt)//二分奇数 特别注意 lt+2
{
int mid=(lt+rt)/2;
if(mid%2==0) mid++;
if(add(mid)) lt=mid;
else rt=mid;
}
int b=begin,e=end;
ans=lt;
lt=1;
if(len1%2==0) rt=len1+1;
else rt=len1;
while(lt+2<rt)//二分偶数
{
int mid=(lt+rt)/2;
if(mid%2==1) mid++;
if(add(mid)) lt=mid;
else rt=mid;
}
if(ans>lt)//比较大小
{
cout<<ans<<endl;
for(int i=b;i<=e;i++)
cout<<s[i];
}
else
{
cout<<lt<<endl;
for(int i=begin;i<=end;i++)
cout<<s[i];
}
return 0;
}