- 浏览: 53286 次
- 性别:
- 来自: 北京
文章分类
最新评论
程序:输入:一行字符串,输出:最长的回文字符的长度以及把它们给输出来。
如: 输入:1596156432111234
输出:6 432111234
回文的性质
首先先把题目撇开,单说回文数的性质,如abcba是一个长度为5的回文数,那它有什么性质呢? 回文数顾名思义,就是从左念和从右念是相同的,也可以说从左遍历和从右遍历是相同的,这些都是废话。因为它是回文数所以可以同时从左和右开始遍历,各 个字符都是相同的。
其实上面那些性质也没什么用,算是铺垫吧,接下来的才是重点,那怎么样去构成一个回文数呢?就用abcba做例子吧,这个回文数的构成是由单个字符c两边同时放置b,构成的bcb再两边同时放置一个a构成的。
回文的判定
那么假设要你判断abcba是不是有两种方法,但是我要说的不是两边同时开始遍历并且判断的方法,再用abcbad做例子吧,用程序判断它是不是一个回文数,我先把过程写出来,然后再把方式写出来。 下面把回文数和回文混用。
首先下标i=0...5,s[i]代表第i个字符。
i从1开始递归,因为第一个字符不存在回文数,
i=1时,当前回文长度为1,就是单个字符b。
当前回文数长度
是我自己定义的名词,就是说以i结尾的回文数的长度。
然后i = 2时,当前回文数是单个字符c,长度为1;
i=3时,这里需要注意一下了,从这里开始就有一些变化了,当前回文数的长度为3,为bcb,
i=4时,当前回文数的长度为5,为abcba,
i=5,当前回文长度为1,是单个字符d,这样它就不是一个回文数。
当前回文数长度
那么求当前回文数的长度(不是标准的语言):
i = 1
while(i 123321吧,
当i = 3时(1233
21
),
start[i] = 2(1
23
321) len[i] = 2;
当i = 5时(123321
),
start[i] = 0(1
23321),len[i] = 6,
也就是说当前回文数的取决于三种情况:
第一种:start[i - 1]的前面一个字符等于i时,当前回文就是(start[i - 1] - 1) ~ i,长度就是len[i - 1] + 2。
第二种:s[i - 1]等于s[i],就是说两个相邻的字符相等的话,那么start[i] = i - 1;len[i] = 2。
第三种:什么都不是,就是单个字符回文,start[i] = i, len[i] = 1。
其实仔细想想可以把len[]这个数组去掉,因为len[i] = i - start[i] + 1;
但是
,因为这篇文章时根据USACO那题写的,那个题目的s[](字符串)中包含空格和标点符号,但是又把它们记入len[]中,所以这个代码只是一个模式,遇到不同的题目要有不同的待遇,但是这种思想我觉得很重要/神奇,类似于DP但又不是。
解题
那么上面的题目就好解了(只给出大致代码):
i = 1, ans = 0
while(i < n)
{
if(s[start[i - 1] - 1] == s[i])
{
start[i] = start[i - 1] - 1;
len[i] = len[i - 1] + 2;
}
else if(s[i - 1] == s[i])
{
start[i] = i - 1;
len[i] = 2;
}
else
{
start[i] = i;
len[i] = 1;
}
if(ans < len[i])
{
ans = len[i];
k = i;
}
}
printf("%d\n", ans);
for(i = start[k]; i <= k; i++)
{
printf("%c", s[i]);
}
发表评论
-
经典面试题
2011-11-22 23:21 633一、请你自我介绍一下 ... -
往年汤森路透上机题
2011-11-15 09:23 1345c++类:main()的标准形式? 在最新的 C99 标准中 ... -
什么是索引?索引有哪几种?
2011-11-10 16:01 1390索引用来快速地寻找那些具有特定值的记录,所有MySQL索引 ... -
Struts 的工作原理
2011-11-06 22:49 814Struts1的流程 服务器启动后,根据web.xml加载A ... -
Java版二叉树遍历非递归程序
2011-10-24 08:18 1002Binary.java import java.util ... -
android 面试题经典
2011-10-22 00:34 5761、 Android dvm的进程和Linux的进程, 应 ... -
恼人的设计模式
2011-10-15 23:20 602最近参加面试,总是被问到设计模式的问题。本人作为一个实用派 ... -
链表相关面试题
2011-10-06 10:46 762题一、 给定单链表,检 ... -
二叉树的算法
2011-10-04 17:37 1902声明,本文所有11道算法题目,覆盖了基本上所有常见的二叉树 ... -
SSH面试题总结
2011-09-28 23:31 605Hibernate工作原理及为什么要用? 原理: 1. ... -
百度2011笔试题
2011-09-27 11:00 6742011年校园招聘笔试题(一) (测试题目答题时间90分钟, ... -
约瑟夫环问题
2011-09-23 16:08 967在一只热气球上有15个日本人和15个美国人,由于热气球超重,必 ... -
联发科技笔试题
2011-09-23 10:20 1097public class Dims { /** ... -
往年EMC编程题答案
2011-09-22 14:24 6771 Write a function to find the ... -
“火柴棍式”程序员面试题
2011-09-21 22:18 915“火柴棍式”程序员面试题 2011年03月21日 星期一 ... -
华为机考
2011-09-21 16:39 14981. 判断回文 public class Huiwen { ... -
《编程之美》读书笔记(一):中国象棋将帅问题
2011-07-16 21:15 682千呼万唤始出来,在 ... -
经典面试题目
2011-07-04 21:06 8681、海量日志数据,提取出某日访问百度次数最多的那个IP。 ... -
关于常见排序算法的稳定性分析和结论
2011-01-14 11:54 623首先,排序算法的稳定 ...
相关推荐
Manacher算法是一位名叫Manacher的人在1975年提出的一种算法,解决的问题是求最长回文子串。Manacher算法的核心思路就是利用之前求得的臂长( 即之前求出的Len值) 来减少时间复杂度,也就是说通过前面求出的Len值来...
长度为N(N很大)的字符串,求最长回文串
Manacher算法:求解最长回文字符串,时间复杂度为O(N) 回文串定义:“回文串”是一个正读和反读都一样的字符串,比如“level”或者“noon”等等就是回文串。回文子串,顾名思义,即字符串中满足回文性质的子串。
输入一个字符串,求出其中最长的回文子串。子串的含义是:在原串中连续出现的字符串片段。回文的含义是:正着看和倒着看相同,如abba和xyyxyyx。在判断时,应该忽略所有标点符号和空格,且忽略大小写,但输出应该...
NULL 博文链接:https://louhaiyun.iteye.com/blog/1328996
查找一个字符串中的最长回文子串,这里采用的是Manacher算法 比如:cababcaac的最长回文子串就是caac 其中的aba bab也都是回文子串 (Manacher算法) 效率很高的一种查找算法,效率可以达到O(2n+1)
字符串处理- 回文串相关- 求最长回文子串.rar
该代码,能够输出用户输入字符串中最常的回文串,可直接在vc6.0平台上运行,不过该代码的效率不高,时间复杂度为o[n^2],希望大家多多指教……
本程序在求字符串最长回文时,摒弃了传统的循环遍历方法,利用三指针对字符串中奇偶回文进行判断,代码效率更高。
最长回文子串问题:给定一个字符串,求它的最长回文子串长度。如果一个字符串正着读和反着读是一样的,那它就是回文串。今天我们就来探讨下这个问题
问题C: 回文串 问题描述: 一篇文章由字母‘A-Z’和’a-z‘、...输出格式:第一行是最长回文串的长度。 第二行是构成最大回文串长的原文。 样例一 输入 输出 Confucius say: Madam, I'm Adam. 11 Madam, I'm Adam
给一个字符串,求出它的一个最长的回文子串.所谓回文子串,指的是一个字符串从左到右和从右到左遍历得到的序列是相同的.例如”abcba”是回文子串,而”abcab”就不是回文子串. 思考 如何确定一个字符串是回文串?这是一...
一个算法中的经典问题,求最长回文子串问题,其实是可以归于二维动态规划问题。 对于给定的一个字符串中,找到这个字符串中的回文子串,回文子串的概念是从前往后正向的读和从后往前反向的读都是完全相同的字符串。
当 mx - i > P[j] 的时候,以S[j]为中心的回文子串包含在以S[id]为中心的回文子串中,由于 i 和j 对称,以S[i]为中心的回文子串必然包含
对于给出的字符串,可截取其前缀和后缀,求能组成的最长回文串。 思路: 正常来说暴力的思路是先匹配前缀pre和后缀suf,找到第一个不匹配的l和r,然后在由l开始从左向右求最长的回文串palindrome,以及由r开始从右向...
80025 判断回文字符串 43 80026 分类统计字符个数 44 夏5周 45 10014 计算函数P(n,x) 45 10016 十进制转换二进制 46 10017 递归函数程序设计求Fabonacci数列 48 10019 改错题error10_1.cpp 49 10022 编程题 50 10026...
构成回文序列最少要增加多少字符 ...解法二为求出字符串与逆序字符串的最长公共子串, 需要增加数目为字符串总数减去最长公共子串长度。 http://blog.csdn.net/ssuchange/article/details/17385039
华为编程大赛,字符串操作代码,关于求一字符串中最长回文串问题的代码……该代码可在VC6.0平台上直接编译通过,运行,按照提示进行数输入一字符串,则可将该字符串中最长的回文串打印输出……里面有注释,希望给...
对于给出的字符串,可截取其前缀和后缀,求能组成的最长回文串。 思路: 正常来说暴力的思路是先匹配前缀pre和后缀suf,找到第一个不匹配的l和r,然后在由l开始从左向右求最长的回文串palindrome,以及由r开始从右向...