最长回文子串
2012-06-14 15:16:46| 分类：
经典编程题
| 标签：
|举报
|字号大中小 订阅
题目：输入一个字符串，求出其中最长的回文子串。子串的含义是：在原串连续出现的字符串片段。回文的含义是：正着看和倒着看是相同的，如abba和 abbebba。在判断是要求忽略所有的标点和空格，且忽略大小写，但输出时按原样输出（首尾不要输出多余的字符串）。输入字符串长度大于等于1小于等于 5000，且单独占一行(如果有多组答案，输出第一组)。
输入：输入一个测试数据n（1<=n<=10）；随后有n行，每行有一个字符串。
输出：输出所要求的回文子串。
样例输入：1
Confuciuss say:Madam,I'm Adam.
样例输出：Madam,I'm Adam
思路：
1、输入字符串buf（gets输入，可能有空格），pri数组记录字母的位置后用res数组记录经过大写转换后的字母。
2、从第i个元素开始遍历，分为两种情况：
回文字串为奇数时，从第i个向左（i-j）向右（i+j）遍历，不相等则跳出。遍历后max记录此次遍历的最大长度，并用x，y记录起点和终点。
回文字串为偶数时，从第i个向左（i-j）向右（i+j+1）遍历，不相等则跳出。
遍历后max记录此次遍历的最大长度，并用x，y记录起点和终点。
3、比较回文字串为奇数和偶数时的最大长度。（下面代码只用max，若偶数大，则更新为偶数的最大值。否则，还是奇数的最大值）
4、用记录最大长度的起点和终点输出最长回文字串。
代码如下：
#include<iostream>
#include<string>
#include<string.h>
#include<cstdio>
#include<ctype.h>
#include<algorithm>
using namespace std;
char buf[5005], res[5005], pri[5005]; //buf输入，res记录buf中字母并转换成大写，pri记录res中字母在buf中位置
int main()
{
//freopen("Input.txt", "r", stdin);
int N;
scanf("%d", &N);
getchar(); //吸收输入N时的输入残余
while(N--)
{
int m = 0, len, max = 0;
int i, j, x, y;
gets(buf); //可能有空格，不能用scanf
len = strlen(buf);
for(i = 0; i < len; ++i)
{
if(isalpha(buf[i])) //判断是否是字母
{
pri[m] = i;
res[m++] = toupper(buf[i]); //字母转换为大写
}
}
for(i = 0; i < m; ++i) //不预先判断奇偶，先奇后偶，max自动更新
{
for(j = 0; i - j >= 0 && i + j < m; ++j) //最长回文字串为奇数
{
if(res[i - j] != res[i + j]) break; //向两边扩展，不相等跳出
if(j * 2 + 1 > max)
{
max = j * 2 + 1; //记录最长回文字串长度
x = pri[i - j]; //记录最长回文字串起点
y = pri[i + j]; //记录最长回文字串终点
}
}
for(j = 0; i - j >= 0 && i + j < m; ++j) //最长回文字串为偶数
{
if(res[i - j] != res[i + j + 1]) break;
if(j * 2 + 2 > max)
{
max = j * 2 + 2;
x = pri[i - j];
y = pri[i + j + 1];
}
}
}
for(i = x; i <= y; ++i) //x，y为起点，终点
{
printf("%c", buf[i]);
}
printf("\n");
}
return 0;
}
另外，附：求回文子串的最大长度O(n^3)代码：
#include<iostream>
#include<string>
#include<string.h>
#include<cstdio>
#include<ctype.h>
#include<algorithm>
using namespace std;
char buf[5005], res[5005];
int main()
{
//freopen("Input.txt", "r", stdin);
int N;
scanf("%d", &N);
getchar();
while(N--)
{
int m = 0, len, max = 0;
int i, j, k;
gets(buf);
len = strlen(buf);
for(i = 0; i < len; ++i)
{
if(isalpha(buf[i]))
{
res[m++] = toupper(buf[i]);
}
}
for(i = 0; i < m; ++i)
{
for(j = i; j < m; ++j)
{
int ok = 1;
for(k = i; k <= j; ++k)
{
if(res[k] != res[i + j - k])
{
ok = 0;
break;
}
}
if(ok && j - i + 1 > max) max = j - i + 1;
}
}
cout<<max<<endl;
}
return 0;
}
评论这张
转发至微博
转发至微博
关闭
玩LOFTER，免费冲印20张照片，人人有奖！
我要抢>
<#--最新日志，群博日志-->
<#--推荐日志-->
<#--引用记录-->
<#--博主推荐-->
<#--随机阅读-->
<#--首页推荐-->
<#--历史上的今天-->
<#--被推荐日志-->
<#--上一篇，下一篇-->
<#-- 热度 -->
<#-- 网易新闻广告 -->
<#--右边模块结构-->
<#--评论模块结构-->
<#--引用模块结构-->
<#--博主发起的投票-->
评论