最长回文子串

时间:2023-02-07 08:44:11

题目:输入一个字符串,求其中最长的回文子串。子串含义:在原串中连续出现的字符串片段。回文的含义就是正着看和倒着看相同,如aabb,yyxyy。在判断时,应该忽略所有出现的标点和空格,且忽略大小写,但应该保持原样输出。输入字符长度不超过5000,且单独占一行。应该输出最长的回文串,如果有多个,输出起始位置最靠左的。


样例输入:Confuciuss say:Madam,I'm Adam.

样例输出:Madam,I'm Adam


分析:

       由于输入的字符串有大写,小写,还有标点空格。直接处理的话会变得非常麻烦。所以我们可以先把字符串,变成一个只有大写字母或者小写字母的字符串。然后再进行后续的判断。又由于题目需要最左的,所以我们从左边开始枚举。

代码如下:

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define MAXN 5000 + 100
char buf[MAXN],s[MAXN];
int p[MAXN];
int main()
{
int n, m = 0, max = 0;
int i, j, x, y;
fgets(buf,sizeof(s),stdin);
//该函数表示从某种流中写入n的字符到某个内存地址,其中stdin表示从键盘流入
n = strlen(buf);
for( i = 0; i < n; i++){
if(isalpha(buf[i])){
p[m] = i; //记录s字符串中字符在buf中的位置
s[m++] = toupper(buf[i]);
}
}
for(i = 0; i < m; i++){ //以 第i个作为回文串的对称中轴
for(j = 0; i-j>=0&&i+j<m; j++){ //当回文串为奇数时
if(s[i-j]!=s[i+j]) break;
if(2*j+1>max){max = 2*j + 1,x = p[i-j],y = p[i+j];}
}
for(j = 0; i-j>=0&&i+j+1<m; j++){//当回文串为偶数时
if(s[i-j]!=s[i+j+1]) break;
if(2*j+2>max){max = 2*j + 2,x = p[i-j],y = p[i+j+1];}
}
}
for(i = x; i<=y; i++)
printf("%c",buf[i]);
printf("\n");
return 0;
}