【ACM】nyoj_132_最长回文子串_201308151713
最长回文子串
- 描述
- 输入一个字符串,求出其中最长的回文子串。子串的含义是:在原串连续出现的字符串片段。回文的含义是:正着看和倒着看是相同的,如abba和abbebba。在判断是要求忽略所有的标点和空格,且忽略大小写,但输出时按原样输出(首尾不要输出多余的字符串)。输入字符串长度大于等于1小于等于5000,且单独占一行(如果有多组答案,输出第一组)。
- 输入
- 输入一个测试数据n(1<=n<=10);
随后有n行,每行有一个字符串。 - 输出
- 输出所要求的回文子串。
- 样例输入
-
1
Confuciuss say:Madam,I'm Adam. - 样例输出
-
Madam,I'm Adam
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define MAX 5500char str[MAX],s[MAX];
int a[MAX];int main()
{
int n;
scanf("%d%*c",&n);
while(n--)
{
int i,j,len1,len2,max,from,to;
gets(str);
len1=strlen(str);
for(i=0,j=0;i<len1;i++)
{
/*if(isalpha(str[i]))
{
if(str[i]<'a')
{s[j]=str[i]+32;a[j++]=i;}
else
{s[j]=str[i];a[j++]=i;}
}*/
if(isalpha(str[i]))
{s[j]=tolower(str[i]);a[j++]=i;}
//isalpha 字符函数 判断ch是否为字母,是返回 1 ,不是,返回 0 ;
//tolower 字符函数 将大写字母转换成小写字母
//toupper 字符函数 将小写字母转换成大写字母
//使用时都需 包含 头文件 <ctype.h>
}
len2=j;max=0;
for(i=0;i<len2;i++)
{
//最长回文子串的长度为奇数 时
for(j=0;i+j<len2&&i-j>=0;j++)
{
if(s[i+j]!=s[i-j])
break;
if(2*j+1>max)
{
max=2*j+1;
from=i-j;
to=i+j;
}
}
//最长回文子串的长度为偶数 时
for(j=0;i+j+1<len2&&i-j>=0;j++)
{
if(s[i+j+1]!=s[i-j])
break;
if(2*j+2>max)
{
max=2*j+2;
from=i-j;
to=i+j+1;
}
}
}
for(i=a[from];i<=a[to];i++)
printf("%c",str[i]);
printf("\n");
}
return 0;
}
最新文章
- $compile
- java集合框架之List
- R 绘图 填充颜色
- tinymce 编辑器 上传图片
- Linux文件系统目录标准
- Java 第四天 Mysql
- C# 解析XML格式的字符串
- 【03】尽可能使用const
- VMware vSphere Client为虚拟机制定物理网卡(图文并茂)
- H5的新应用-获取用户当前的地理坐标
- [HNOI2012]射箭
- LeetCode(28): 实现strStr()
- 2016年3月11日Android学习日记
- random 模块 时间模块(time) sys模块 os模块
- zoj Beautiful Number(打表)
- Codeforces292D(SummerTrainingDay06-L 前缀并查集)
- JAVA 对基础知识的加强
- C++缓冲区溢出
- C++ Word Count 发布程序
- ros 查找包路径