题目描述:
输入一个字符串,求出其中最长的回文子串。子串的含义是:在原串连续出现的字符串片段。回文的含义是:正着看和倒着看是相同的,如abba和abbebba。在判断是要求忽略所有的标点和空格,且忽略大小写,但输出时按原样输出(首尾不要输出多余的字符串)。输入字符串长度大于等于1小于等于5000,且单独占一行(如果有多组答案,输出第一组)。
样例输入: Confuciuss say: Madam, I'm Adam.
样例输出: Madam, I'm Adam
其中,回文的意思是指字母构成回文,所以处理的时候需要把除字母外的符号先忽略掉。可以用cctype或者ctype.h头文件中的isalpha函数判断其是否为字母。
其次,也无需考虑字母的大小写,于是可用上述头文件的toupper或者tolower将其中的字符统一转换成大写或小写。
huiwen.cpp
#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
using namespace std;
#define MAXN 1000000+20
char ch1[MAXN];
char ch2[MAXN];
int ch2x[MAXN];
int main()
{
int c = 1;
while(fgets(ch1,MAXN,stdin),ch1[strlen(ch1)-1] = '\0',strcmp(ch1,"END"))
{
int sl = strlen(ch1),max = 0;
int ss = 0,ee = 0;
int maxx = 1;
/*
for(int i = 0;i < strlen(ch1);i++)
{
if (isalpha(ch1[i]))
{
ch2[sl] = toupper(ch1[i]);
ch2x[sl++] = i;
}
}
*/
for(int i = 0;i < sl && maxx;i++)
{
for(int j = i;j < sl && maxx;j++)
{
int ok = 1;
for(int k = i;k <= j && maxx;k++)
{
if (ch1[k] != ch1[i+j-k])
{
ok = 0;
break;
}
}
if (ok&& j-i+1 > max)
{
max = j-i+1;
ss = i;
ee = j;
}
}
if (sl - i - 1 <= max)
{
maxx = 0;
}
}
/*
for(int i = 0;i < ee - ss + 1;i++)
{
printf("%c",ch2[ss+i]);
}
printf("\n");
*/
/*
for(int i = 0;i < ch2x[ee] - ch2x[ss] + 1;i++)
{
printf("%c",ch1[ch2x[ss]+i]);
}
*/
printf("Case %d: %d\n",c++,max);
}
return 0;
}