C-最长回文子串(1)

最长回文子串，就是在字符串中找到最长的对称的子串。

s是一个字符串。

int max = 0;

for(i = 0;i<m;i++)

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

　　　　if(s[i.....j]是回文子串 && j-i+1 >max) max = j-i+1;

这样就找到了，最长回文子串，而且回文子串的位置就找到了，即s[i......j]

剩下的工作就是如何判断s[i......j]是不是回文的问题了。

判断是不是回文，就要看该子串是不是对称。

所以问题就解决了！

注：字符串的读取方式.首先不能使用scanf();他会遇见回车、空格结束输入。

还有就是gets(s)，但是他没有标明要输入字符串的长度，这就出现了一个潜在的问题就是，gets将不停地往s里面塞东西，而不管能不能塞得下。这就可能会导致出现内存问题。

选择使用fgets()他会一次性的读取一行。

　　从文件结构体指针stream中读取数据，每次读取一行。读取的数据保存在buf指向的字符数组中，每次最多读取bufsize-1个字符（第bufsize个字符赋'\0'），如果文件中的该行，不足bufsize个字符，则读完该行就结束。函数成功将返回buf，失败或读到文件结尾返回NULL。因此我们不能直接通过fgets的返回值来判断函数是否是出错而终止的，应该借助feof函数或者ferror函数来判断。

函数原型：char *fgets(char *buf, int bufsize, FILE *stream);

参数：

*buf: 字符型指针，指向用来存储所得数据的地址。

bufsize: 整型数据，指明buf指向的字符数组的大小。

*stream: 文件结构体指针，将要读取的文件流。

虽然说是读取文件流，但是也可以从标准输入输出来输入,即键盘输入stdin.

fgets(char*buf,int bufsize,stdin)z这样就可以实现从键盘输入了。

以下是详细代码部分：

#include<stdio.h>

#include<string.h>

#include<ctype.h>

#define MAXN 5000+10

char buff[MAXN],s[MAXN];

int main()

{

    int n,m = ,max = ;

    int i ,j,k;

    fgets(buff,sizeof(s),stdin);

    n = strlen(buff);

    for(i = ;i<n;i++)

    {

        if(isalpha(buff[i]))

        s[m++] = toupper(buff[i]);//去除其中的非字母字符

    }

    printf("n = %d\n",n);

    for(i = ;i<m;i++)

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

        {

            int ok = ;

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

            {

                if(s[k] != s[i+j-k])ok = ;

            }

            if(ok && j-i+>max) max = j-i+;

        }

    printf("i = %d,j = %d,max = %d\n",i,j,max);

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

     //   printf("%c ",buff[k]);

    return ;

}

这种方法虽然可以初步解决了最长回文子串的查找工作，但是效率还不是很高……

巴特西

C-最长回文子串(1)

最新文章

热门文章