题解 P1210 【回文检测】
ShineEternal
2019-07-07 09:03:21
看到其他解法都是dp，马拉车等等，虽然有一篇和我的思路差不多，但是代码实现上有些差别，所以来分享一下。
# 分析：
如果我们枚举左右端点的话，时间复杂度就接近立方级别，于是我们利用回文串的性质，可以根据它的对称中心了枚举，大体能降到平方级别。
> code
```cpp
#include<cstdio>
#include<iostream>
#include<string>
using namespace std;
struct ben
{
char cha;
int num;
}a[20100];
int main()
{
string line;
string s;
while(getline(cin,line))
{
s+=line;
s+="\n";
}
int cnt=0;
for(int i=0;i<s.length();i++)
{
if(isalpha(s[i]))
{
a[cnt].cha=toupper(s[i]);
a[cnt].num=i;
cnt++;
}
}
int ans=0,l,r;
for(int i=0;i<cnt;i++)
{
int j=1,sum=1;
while(i>=j&&i+j<cnt)
{
if(a[i-j].cha==a[i+j].cha)
{
sum+=2;
if(sum>ans)
{
ans=sum;
l=i-j;
r=i+j;
}
}
else
break;
j++;
}
j=0,sum=0;
while(i>=j&&i+j+1<cnt)
{
if(a[i-j].cha==a[i+j+1].cha)
{
sum+=2;
if(sum>ans)
{
ans=sum;
l=i-j;
r=i+j+1;
}
}
else
break;
j++;
}
}
int last=0;
for(int i=a[l].num;i<=a[r].num;i++)
{
if(isalpha(s[i]))last++;
}
printf("%d\n",ans);
for(int i=a[l].num;i<=a[r].num;i++)cout<<s[i];
return 0;
}
```
**关于读入输出的代码优化借鉴了网上一篇blog，在此orz一下**