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个字符赋''），如果文件中的该行，不足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 = 0,max = 0;
    int i ,j,k;
    fgets(buff,sizeof(s),stdin);
    n = strlen(buff);
    for(i = 0;i<n;i++)
    {
        if(isalpha(buff[i]))
        s[m++] = toupper(buff[i]);//去除其中的非字母字符
    }
    printf("n = %d
",n);
    for(i = 0;i<m;i++)
        for(j = i;j<m;j++)
        {
            int ok = 1;
            for(k = i;k<=j;k++)
            {
                if(s[k] != s[i+j-k])ok = 0;

            }
            if(ok && j-i+1>max) max = j-i+1;
        }
    printf("i = %d,j = %d,max = %d
",i,j,max);
    //for(k = i;k<=j;k++)
     //   printf("%c ",buff[k]);

    return 0;
}

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