文档章节

最长回文子串

哭哭吓唬你
 哭哭吓唬你
发布于 2014/03/27 22:28
字数 516
阅读 43
收藏 0

分析:

1. 保证读入的字符串为一行(不要被空格隔断),使用fgets(char *s, int count, FILE *stream)函数输入。

2. 字符串预处理,去除所有的标点和空格,并忽略大小写,成为一个新串,同时记录新串中的字符在原串中的位置;

3. 判断子串是否是回文串,设定i为子串的中间位置,不断向两侧同时延伸。主要:子串的长度分为奇数和偶数两种情况。

代码如下:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctype.h>
using namespace std;
#define LEN 5000 + 10
int main() {

	char str[LEN];
	char s[LEN];
	while (fgets(str, sizeof(s), stdin) != NULL) {

		//字符位置标记数组
		//用于标记s中的字符在str中的位置
		int pos[LEN];
		//原串中最长回文子串的起止位置
		unsigned begin, end;

		unsigned i, j, index;
		//预处理字符串,去除标点符号等无关字符
		for (i = 0, index = 0; i < strlen(str); i++) {
			if (isalpha(str[i])) {
				s[index] = toupper(str[i]);
				pos[index++] = i;
			}
		}

		for (i = 0; i < index; i++) {
			printf("%d ", pos[i]);
		}
		printf("\n");
		printf("%s\n", s);
		printf("%d\n", strlen(s));
		printf("%d\n", index);

		//检查字串是否是回文串
		//从字串中间部分向两侧延伸:子串长度为奇数,子串长度为偶数
		//i为字串中间位置
		unsigned maxLen = 0;
		for (i = 0; i < index; i++) {

			//字串长度为奇数
			for (j = 0; i - j >= 0 && i + j < index; j++) {
				if (s[i - j] != s[i + j]) {
					break;
				}
				if (j * 2 + 1 > maxLen) {
					maxLen = j * 2 + 1;
					begin = pos[i - j];
					end = pos[i + j];
				}
			}

			//字串长度为偶数
			for (j = 0; i - j >= 0 && i + j + 1 < index; j++) {
				if (s[i - j] != s[i + j + 1]) {
					break;
				}
				if (j * 2 + 2 > maxLen) {
					maxLen = j * 2 + 2;
					begin = pos[i - j];
					end = pos[i + j + 1];
				}
			}

		}

		for (i = begin; i <= end; i++) {
			printf("%c", str[i]);
		}
		printf("\n");
		printf("%d\n", (end - begin + 1));

		fflush(stdout);
	}
	return 0;
}



测试数据:


输入:xiaomanzhu says:Madam,I'm Adam

输出:Madam,I'm Adam



© 著作权归作者所有

哭哭吓唬你
粉丝 4
博文 101
码字总数 40066
作品 0
石景山
程序员
私信 提问
加载中

评论(1)

xiaav
xiaav
马拉车算法(或者叫曼彻斯特算法):http://www.rudy-yuan.net/archives/130/
马拉车算法(Manacher's Algorithm)

这是悦乐书的第343次更新,第367篇原创 Manacher's Algorithm,中文名叫马拉车算法,是一位名叫Manacher的人在1975年提出的一种算法,解决的问题是求最长回文子串,神奇之处在于将算法的时间...

小川94
06/04
0
0
lintcode最长回文子串(Manacher算法)

题目来自lintcode, 链接:http://www.lintcode.com/zh-cn/problem/longest-palindromic-substring/ v最长回文子串 给出一个字符串(假设长度最长为1000),求出它的最长回文子串,你可以假定...

余二五
2017/11/16
0
0
leetcode——最长回文子串

关于这道题,我的第一想法是针对回文串的特性,对字符串的每个字符(奇数回文串)或者每两个字符(偶数回文串)向两边开始扩展分析。在这个过程中不断发现最新的最长回文串。显然这个算法的复...

wikison
2015/08/20
491
0
前端分享会--从一道算法题目开始的学习

算法题 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 理解 所谓回文,就是字符串反过来或者顺着念都是一样的。这就意味着我们可以通过字符串与反向排序之后...

ziven先生
04/15
0
0
Manacher's Algorithm 马拉车算法

这个马拉车算法Manacher‘s Algorithm是用来查找一个字符串的最长回文子串的线性方法,由一个叫Manacher的人在1975年发明的,这个方法的最大贡献是在于将时间复杂度提升到了线性,这是非常了...

机器的心脏
2017/12/02
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OpenStack 简介和几种安装方式总结

OpenStack :是一个由NASA和Rackspace合作研发并发起的,以Apache许可证授权的自由软件和开放源代码项目。项目目标是提供实施简单、可大规模扩展、丰富、标准统一的云计算管理平台。OpenSta...

小海bug
昨天
5
0
DDD(五)

1、引言 之前学习了解了DDD中实体这一概念,那么接下来需要了解的就是值对象、唯一标识。值对象,值就是数字1、2、3,字符串“1”,“2”,“3”,值时对象的特征,对象是一个事物的具体描述...

MrYuZixian
昨天
6
0
数据库中间件MyCat

什么是MyCat? 查看官网的介绍是这样说的 一个彻底开源的,面向企业应用开发的大数据库集群 支持事务、ACID、可以替代MySQL的加强版数据库 一个可以视为MySQL集群的企业级数据库,用来替代昂贵...

沉浮_
昨天
4
0
解决Mac下VSCode打开zsh乱码

1.乱码问题 iTerm2终端使用Zsh,并且配置Zsh主题,该主题主题需要安装字体来支持箭头效果,在iTerm2中设置这个字体,但是VSCode里这个箭头还是显示乱码。 iTerm2展示如下: VSCode展示如下: 2...

HelloDeveloper
昨天
7
0
常用物流快递单号查询接口种类及对接方法

目前快递查询接口有两种方式可以对接,一是和顺丰、圆通、中通、天天、韵达、德邦这些快递公司一一对接接口,二是和快递鸟这样第三方集成接口一次性对接多家常用快递。第一种耗费时间长,但是...

程序的小猿
昨天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部