题解 P1210 【[USACO1.3]最长的回文 Calf Flac】
GenshinPlayer123 · · 题解
题目传送门：P1210 [USACO1.3]最长的回文 Calf Flac
这道题就是找一段话中最长的回文
首先，我们可以看一下样例：
输入：
Confucius say: Madam, I'm Adam.输出：
11
Madam, I'm Adam前置知识：
1：字符串基本
在c++中，字符串有两种
1.c数组
c数组是c语言中的字符串，也可以在c++中用 例
#include<iostream>
using namespace std;
int main()
{
char a[200];//定义一个c字符串，名为a
cin>>a;//输入
//scanf("%s",a);
cout<<a;//输出
//printf("%s",a);
return 0;
} 注意：在用scanf读入时，没有取地址符 c数组不用加任何多余的头文件，但有个 叫“cstring”的头文件，有更多关于c数组 的函数
#include<cstring>
#include<cstdio>
using namespace std;
char a[100],b[100];
int main()
{
strcpy(a,"I Ak IOI");//将"I AK IOI"拷贝到a中
printf("%s,len=%d\n",a,strlen(a));//输出a和a的长度
scanf("%s",b);
if(strcmp(a,b)==0)//比较a和b的字典序,a>b返回1,a=b返回0,a<b返回-1
printf("%s=%s",a,b);
if(strstr(a,b)!=NULL)//查找字串
printf("%s is a substr of %s\n",b,a) ;
return 0;
} 2.string
c++由于类的存在，引入了string类，需要“string”头文件 例：
#include<cstdio>
#include<string>
using namespace std;
int main()
{
string a;//定义了一个字符串a
scanf("%s",a) ;//不读空格
getline(cin,a);//正行读入,可读入空格
a+="AK IOI";//在a后面接入“AK IOI”
printf("%d",a.size())//输出a的长度
printf("%c",a[1])//输出a[1]
return 0;
}3.如何遍历字符串
由于字符串都是以'\0'结尾，所以可以这样遍历：
#include<cstdio>
using namespace std;
char a[]={'I',' ','A','K',' ','I','O','I','\0'};//字符串以\0结尾
int main()
{
printf("%s",a);
for(int i=0;a[i]!='\0';i++)//当a[i]不是\0，也就是a没结束
{
/*相关操作*/
}
return 0;
} 选自原来的题解：https://www.luogu.com.cn/blog/huangjinyang2019/solution-uva1585
2.字符串回文
假设有一个字符串：
chenzheakIoIkaehznehc那如何判断这个字符串是不是回文串呢？
首先找到中间值，为length/2
chenzheakI|oIkaehznehc然后，我们可以找一下对应关系：
c h e n z h e a k I | o I k a e h z n e h c
1 2 3 4 5 6 7 8 9 10 1+10 2+10 3+10...于是我们可以发现，第i个元素对应着第i+length/2个元素，假如发现一个不相等的，就return false；
示例代码：
bool hui(char[] pur,int length)
{
for(int i=0;i<length/2;i++)
{
if(pur[i+st]!=pur[st+length-i-1])
return false;
}
return true;
}然后有了这些，就可以切题了
题目
我们可以分成几个部分
1.读入
我们不知道这个奶牛打的文章有多长，所以可以用大家熟知的while循环+cin.getline读入发。这样遇到EFOAFO UFO的时候就能停止读入。
但是我们在输出时，换行也要输出。那我们就可以手动加上
例：
while(cin.getline(line,88))
{
strcat(org,line);
strcat(org,"\n");
}2.处理
题目中说要把除了大小写字母之外的都删除，但输出时又要输出原文，所以我们可以用一个pos数组记录变化前的位置，输出时用它就可以了
例：
int length=strlen(org),pl=0;
for(int i=0;i<length;i++)
{
if(org[i]>='a'&&org[i]<='z')
{
pur[pl]=org[i];
pos[pl]=i;
pl++;
}
if(org[i]>='A'&&org[i]<='Z')
{
pur[pl]=org[i]+32;
pos[pl]=i;
pl++;
}
}3.找回文头和长度
这个我就不详细说了，用两层for循环即可
bool chk(int st,int length)
{
if(st+length>pl)return false;
for(int i=0;i<length/2;i++)
{
if(pur[i+st]!=pur[st+length-i-1])
return false;
}
return true;
}
int maxn=-1,st=0;
for(int i=0;i<pl;i++)//回文头
{
for(int j=maxn+1;j<=2010;j++)//长度
{
if(chk(i,j)&&j>maxn)
{
maxn=j;
st=i;
}
}
}4.输出
还记得之前的pos么？现在找出回文头和尾在原始串里的位置，然后输出这一段即可
cout<<maxn<<endl;
for(int i=pos[st];i<=pos[st+maxn-1];i++)
{
cout<<org[i];
}最后上完整程序：
#include<iostream>
#include<cstring>
using namespace std;
char org[200001];
char line[90];
int pos[200001];
char pur[200001];
int pl=0;
bool chk(int st,int length)
{
if(st+length>pl)return false;
for(int i=0;i<length/2;i++)
{
if(pur[i+st]!=pur[st+length-i-1])
return false;
}
return true;
}
int main()
{
while(cin.getline(line,88))
{
strcat(org,line);
strcat(org,"\n");
}
int length=strlen(org);
for(int i=0;i<length;i++)
{
if(org[i]>='a'&&org[i]<='z')
{
pur[pl]=org[i];
pos[pl]=i;
pl++;
}
if(org[i]>='A'&&org[i]<='Z')
{
pur[pl]=org[i]+32;
pos[pl]=i;
pl++;
}
}
int maxn=-1,st=0;
for(int i=0;i<pl;i++)
{
for(int j=maxn+1;j<=2010;j++)
{
if(chk(i,j)&&j>maxn)
{
maxn=j;
st=i;
}
}
}
cout<<maxn<<endl;
for(int i=pos[st];i<=pos[st+maxn-1];i++)
{
cout<<org[i];
}
return 0;
}bye~~