首页 > 代码库 > 回文字符串

回文字符串

2024-07-03 05:53:05   229人阅读

输入一个字符，求出其中最长的回文子串。子串的含义是：在元串中连续出现的字符串片段。回文的含义是：正看和倒看相同，如abba和yyxyy，在判断时候应该忽略所有的空格和标点符号，且忽略大小写，但输出应该保持原样，输入的字符长度不超过5000，且占据单独一行，输出最长的回文子串
如有多个，输出，起始位置最靠左的
样例输入：Confuciuss say：Mandam,I ˊm Adam.
样例输出：Madam，I ˊm Adam


关于输入:

对大小写统一处理成大写, 其余符号全都去除,  因为有此会造成各字符在字符串中位置的变化, 所以用一个数组保存新串中各位置的字符在原串中的位置.

判断回文:

    考虑 aba 和abba 两种情况即可.
   
#include<stdio.h>
#include<string.h>
#include<ctype.h>
#define MAXN 5000+10
char buf[MAXN],s[MAXN];
int p[MAXN];
int main()
{
int n,m=0,max=0,x,y;
int i,j;
fgets(buf,sizeof(s),stdin);
n=strlen(buf);
for(i=0;i<n;i++)
{
if(isalpha(buf[i]))
{
p[m]=i;
s[m++]=toupper(buf[i]); 
}

}
for(i=0;i<m;i++)
{
for(j=0;i-j>=0&&i+j<m;j++)
{
if(s[i-j]!=s[i+j])break;
if(j*2+1>max){max=j*2+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(j*2+2>max){max=j*2+2;x=p[i-j];y=p[i+j+1];}
}
}
for(i=x;i<=y;i++)
printf("%c",buf[i]);
printf("\n");
return 0;
}


联系
我们