A-A+

最长回文子串

2012年09月09日 动态规划 暂无评论 阅读 171 次

最长回文子串

时间限制:1000 ms  |  内存限制:65535 KB
难度:4
 
描述
输入一个字符串,求出其中最长的回文子串。子串的含义是:在原串连续出现的字符串片段。回文的含义是:正着看和倒着看是相同的,如abba和abbebba。在判断是要求忽略所有的标点和空格,且忽略大小写,但输出时按原样输出(首尾不要输出多余的字符串)。输入字符串长度大于等于1小于等于5000,且单独占一行(如果有多组答案,输出第一组)。
 
输入
输入一个测试数据n(1<=n<=10);
随后有n行,每行有一个字符串。
输出
输出所要求的回文子串。
样例输入
1
Confuciuss say:Madam,I'm Adam.
样例输出
Madam,I'm Adam

伪代码如下,大家自己调试下,参考ACM程序设计原书!

[cpp]

#include <stdio.h>
#include <string>
#include <string.h>
#include <ctype.h>
#define MAXN 5000+10
char buf[MAXN],s[MAXN];//buf为输入的字符串,s为忽略标点的字符串
int p[MAXN];//p数组记录新数组在原数组中的坐标
int main()
{
    int n,m,max,x,y;
    int i,j,t;
    scanf("%d",&t);
    while(t--)
    {
    m=max=0;
    fgets(buf,sizeof(s),stdin);//==string->getline();
    printf("abcdefgn");
    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;
}
//算法参考程序设计原书
[/cpp]

标签:

给我留言

Copyright © C/C++程序员之家 保留所有权利.   Theme  Ality 浙ICP备15011757号-3

用户登录