输入一个字符，求出其中最长的回文子串。子串的含义是：在元串中连续出现的字符串片段。回文的含义是：正看和倒看相同，如abba和yyxyy，在判断时候应该忽略所有的空格和标点符号，且忽略大小写，但输出应该保持原样，输入的字符长度不超过5000，且占据单独一行，输出最长的回文子串
如有多个，输出，起始位置最靠左的
样例输入：Confuciuss say：Mandam,I ˊm Adam.
样例输出：Madam，I ˊm Adam
1.输入问题的解决
scanf（"%s",s）;已经不适合，因为它碰到空格或则TAB键就会停下来，fgetc（）函数读入的是一个个字符，而非完整的字符串，所以在这里采用fgets(buf,MAXN,fin)
从流中读一行或指定个字符，
原型是char *fgets(char *s, int n, FILE *stream);
从流中读取n-1个字符，除非读完一行，参数s是来接收字符串，如果成功则返回s的指针，否则返回NULL。
形参注释：*s结果数据的首地址；n-1:一次读入数据块的长度,其默认值为1k，即1024;stream文件指针
char * fgets(char * s,int size,FILE * stream);
s，数据存储位置；size，读取字符串的最大数量；stream，指向FILE结构的指针。
2 这个函数的精妙之处在于它所需要的预处理
在输入完成后，必须要过滤掉，空格和其他的标点符号，所以这就需要提取出有用的字符，而去除那些无用的字符，通过这样的操作，就能很好解决问题。
就拿刚才的题目中给的例子而言，我们去除空格和标点符号之后的字符串为：CONFUCIUSSSAYMADAMIMADAM主要母的就是这个字符串中的字符串的最大回文子串，这就很明显了。
如下面简易代码所示
n=strlen(buf);
m=0;
for(i=0;i
if(isalpha(buf[i])) s[m++]=toupper(buf[i]);
其中isalpha（）函数是用来判断是不是为大写字母或则小写字母，toupper（）函数返回字符的大写形状，它们都在命名空间ctype.h中。
祥情见
工具的问题基本解决，那么现在触碰核心的回文子串的查找方法.
1 常规方法
for(i=0;i
for(j=i;j
{
int ok=1;
for(k=i;k
if(s[k]!=s[i+j-k]) ok=0;
if(ok&&j-i+1>max)
max=j-i+1;
}
总的来看，这种方法求出的绘文字串太过于复杂
2
这种方法的核心思想为从第一个开始当做回文子串的中间字母开始
向两边查找，只要不符合情况就break
这种有两种情况
1.adfda ad和da相对于f对称
2.asddsa asd和dsa直接对称
for(i=0;i {
//直接对称的情况
for(j=0;i-j>=0&&i+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 {
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];}
}
}
这种方法跳过了很多没有必要的运算 所以其执行效率更高！
回文子串的可源代码
#include
#include
#include
#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 {
if(isalpha(buf[i]))
{
p[m]=i;
s[m++]=toupper(buf[i]);
}
}
for(i=0;i {
for(j=0;i-j>=0&&i+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 {
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;
}
阅读(8790) | 评论(0) | 转发(0) |
