自动搬运

查看原文

来自洛谷，原作者为

	GenshinPlayer123 超级无敌原神大王

搬运于2025-08-24 21:22:28，当前版本为作者最后更新于2020-03-21 20:58:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目传送门：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~~