NYOJ-132 最长回文子串

最长回文子串

时间限制：1000ms | 内存限制：65535KB难度：4

描述

输入一个字符串，求出其中最长的回文子串。子串的含义是：在原串连续出现的字符串片段。回文的含义是：正着看和倒着看是相同的，如abba和abbebba。在判断是要求忽略所有的标点和空格，且忽略大小写，但输出时按原样输出（首尾不要输出多余的字符串）。输入字符串长度大于等于1小于等于5000，且单独占一行(如果有多组答案，输出第一组)。

输入

输入一个测试数据n（1<=n<=10）；

随后有n行，每行有一个字符串。

输出

输出所要求的回文子串。

样例输入

1
Confuciuss say:Madam,I'm Adam.

样例输出

Madam,I'm Adam

1 /* 功能Function Description:     NYOJ-132  最长回文子串
 2    开发环境Environment:          DEV C++ 4.9.9.1
 3    技术特点Technique:
 4    版本Version:
 5    作者Author:                    可笑痴狂
 6    日期Date:                      20120730
 7    备注Notes:                    注意题目要求是忽略大小写和标点符号的，所以要事先做预处理
 8 */
 9 #include<stdio.h>
10 #include<string.h>
11 #include<ctype.h>   
12 #define MAX 5010
13 
14 int main()
15 {
16     int t,i,j,st,len,end,k,max;
17     int pos[MAX];
18     char s[MAX],s1[MAX];
19 
20     scanf("%d",&t);
21     getchar();
22     while(t--)
23     {
24         gets(s);
25         len=strlen(s);
26         k=st=max=end=0;        
27         for(i=0;i<len;++i)          //预处理
28         {
29             if(isalpha(s[i]))       //判断是不是字母 包含在头文件ctype.h中
30             {
31                 pos[k]=i;           //存数位置
32                 if(s[i]<97)         //把大写转化为小写字母
33                     s1[k++]=s[i]+32;
34                 else
35                     s1[k++]=s[i];
36             }
37         }
38             //    puts(s1);
39             //    for(i=0;i<k;++i)
40             //        cout<<pos[i];
41             //    cout<<endl;
42         for(i=0;i<k;++i)
43         {    
44             for(j=0;j<=i&&i+j<k;++j)        //回文字符数位奇数的情况
45             {
46                 if(s1[i-j]!=s1[i+j])
47                     break;
48                 if(j*2+1>max)
49                 {
50                     max=2*j+1;
51                     st=pos[i-j];
52                     end=pos[i+j];
53                 }
54             }
55             for(j=0;j<=i&&i+j+1<k;++j)     //回文字符数为偶数的情况
56             {
57                 if(s1[i-j]!=s1[i+j+1])
58                     break;
59                 if(j*2+2>max)
60                 {
61                     max=2*j+2;         
62                     st=pos[i-j];
63                     end=pos[i+j+1];
64                 }
65             }
66         }
67         for(i=st;i<=end;++i)
68             printf("%c",s[i]);
69         printf("\n");
70     }
71     return 0;
72 }

原文链接: https://www.cnblogs.com/dongsheng/archive/2012/07/30/2615564.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍