[code]最长回文子串

分析：

不能用scanf（“%s”）,因为碰到空格或者Tab就会停下来。

解决输入中有空格

方法一：使用fgetc（fin），读取一个打开的文件fin，读取一个字符，然后返回一个int值，当文件结束，返回特殊标记EOF(int型的)。

（使用fgetc(fin)可以从打开的文件fin中读取一个字符，一般情况下，应当在检查它不是EOF后再将其转化成为char值。从标准输入读取一个字符可以用getchar(),等价于fgetc(sdin)）。

方法二：使用fgets(buf,MAXN,fin)读取完整的一行，其中buf声明为char buf[MAXN]。这个函数读取不超过MAXN-1个字符，然后在末尾添上结束符‘\0’，因此不会出现越界情况。一旦读到回车'\n'，读取工作会停止。并将'\n'作为最后一个有效字符。

解决判断时候忽略标点，输出却要保持原样。

分析：不能直接删除，不然不能输出。

预处理：构造新的字符串，不包含原来的标点符号，而且所有字符变成大写。

n=strlen(buf);

m=0;

for(i=0;i<len;i++){if(isalpah(buf[i]))s[m++]=toupper(buf[i]);}

Note:使用了ctype.h中的isalpha(c)函数，用于判断字符是否是大写或者小写，用toupper(c)返回c的大写形式。

这样处理以后buf保存的就是原字符串中的所有字母了。（符号被删去）

isalpha,isdigit,isprint

枚举回文串的起点和终点

max记录最长回文子串的长度。如果串s的第i个字符到第j个字符是回文串，检查长度j-i+1是否超过max。

//----------------------------------------------------------------

#include<time.h>

#include<stdio.h>

#include<string.h>

#include<ctype.h>

#define MAXN 5000 + 10

char buf[MAXN], s[MAXN];

int p[MAXN];

int main(){

int i,j,k,n,m=0,max=0,x=0,y=0;

fgets(buf,MAXN,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=i;j<m;j++)

{

//判D断?i到??j是??不?是??回?文?

int ok=1;

for(k=i;k<j;k++)

{

if(s[k]!=s[j+i-k]){ok=0;break ;}

}

if(ok && max<j-i+1)

{

max=j-i+1;

x=p[i];

y=p[j];

}

for(i=x;i<y;i++)

printf( "%c",buf[i]);

printf( "Time used=%.21f\n",(double )clock()/CLOCKS_PER_SEC);

}

巴特西

[code]最长回文子串

最新文章

热门文章