Calf Flac
It is said that if you give an infinite number of cows an infinite number of heavy-duty laptops (with very large keys), that they will ultimately produce all the world's great palindromes. Your job will be to detect these bovine beauties.
Ignore punctuation, whitespace, numbers, and case when testing for palindromes, but keep these extra characters around so that you can print them out as the answer; just consider the letters `A-Z' and `a-z'.
Find the largest palindrome in a string no more than 20,000 characters long. The largest palindrome is guaranteed to be at most 2,000 characters long before whitespace and punctuation are removed.
PROGRAM NAME: calfflac
INPUT FORMAT
A file with no more than 20,000 characters. The file has one or more lines which, when taken together, represent one long string. No line is longer than 80 characters (not counting the newline at the end).
SAMPLE INPUT (file calfflac.in)
Confucius say: Madam, I'm Adam.
OUTPUT FORMAT
The first line of the output should be the length of the longest palindrome found. The next line or lines should be the actual text of the palindrome (without any surrounding white space or punctuation but with all other characters) printed on a line (or more than one line if newlines are included in the palindromic text). If there are multiple palindromes of longest length, output the one that appears first.
SAMPLE OUTPUT (file calfflac.out)
11 Madam, I'm Adam
题意:
给出一个字符串句子,找出这个字符串最大的回文串数量,并输出这个回文串语句(判断回文串是不包括标点符号和空格在内的)。
思路:
一个个点进行查找,从该点开始向左右扩展找出最大回文串值,并记录首和尾的位置。回文串分为两种情况,分别为奇数和偶数的情况,分别计算和统计。
first and wrong:
#include<stdio.h> #include<string.h> #include<stdlib.h> #define BOR 20000+5 int same(char a,char b) { if(a==b) return 1; if(a==b-32) return 1; if(a-32==b) return 1; return 0; } int main() { char pos[BOR]; int i,length,max=0,l,r,sum,from,to; gets(pos); length=strlen(pos); // printf("\n%s\n",pos); //循环不是从0开始的,所以如果数组只有pos[0]的话,则程序会出现错误 for(i=1;i<length;i++) { if((pos[i]<'A'||pos[i]>'Z')&&(pos[i]<'a'||pos[i]>'z')) continue; l=i-1; r=i+1; sum=1; //这是只有回文串是单数的时候的情况 // printf("\nr=%d\n",r); // printf("%c",pos[11]); while((pos[l]<'A'||pos[l]>'Z')&&(pos[l]<'a'||pos[l]>'z')&&l>=0) l--; while((pos[r]<'A'||pos[r]>'Z')&&(pos[r]<'a'||pos[r]>'z')&&(r<length)) r++; //这里的判断条件没有=,细心! // printf("\nl=%d\nmid=%d\nr=%d\n",l,i,r); // system("pause"); while(l>=0&&r<length&&same(pos[l],pos[r])) { sum+=2; l--; r++; while((pos[l]<'A'||pos[l]>'Z')&&(pos[l]<'a'||pos[l]>'z')&&l>=0) l--; while((pos[r]<'A'||pos[r]>'Z')&&(pos[r]<'a'||pos[r]>'z')&&r<length) r++; // printf("\nl=%d\nr=%d\n",l,r); // printf("sum=%d\n",sum); // system("pause"); } if(sum>max) { max=sum; from=l+1; to=r-1; } // printf("\nl=%d\nr=%d\n",l,r); // printf("max=%d\n",max); // system("pause"); } // printf("\nfrom=%d\nto=%d\n",from,to); while((pos[from]<'A'||pos[from]>'Z')&&(pos[from]<'a'||pos[from]>'z')&&from>=0) from++; while((pos[to]<'A'||pos[to]>'Z')&&(pos[to]<'a'||pos[to]>'z')&&to<length) to--; //方法可行 //但是存在许多容易出错的地方,而且循环从1开始,故会忽略许多情况 //比如但数组长度只有1的时候 printf("%d\n",max); for(from;from<=to;from++) printf("%c",pos[from]); printf("\n"); // system("pause"); return 0; }AC:
#include<stdio.h> #include<string.h> #define BOR 20000+5 //判断是否相等的函数 int same(char a,char b) { if(a==b||a-32==b||a==b-32) return 1; return 0; } int main() { freopen("calfflac.in","r",stdin); freopen("calfflac.out","w",stdout); char pos[BOR]={0},cr[BOR]={0}; char line[85]; int length,i,l,r; int from,to,max=0,sum; //输入部分,看清题意应如何输入字符串的 while(gets(line)!=NULL) { strcat(pos,line); cr[strlen(pos)-1]=1; } length=strlen(pos); for(i=0;i<length;i++) { if((pos[i]<'A'||pos[i]>'Z')&&(pos[i]<'a'||pos[i]>'z')) continue; //当回文串为奇数的时候 l=i; r=i; sum=-1; //巧设,令一开始都为自己本身,长度为-1 while(l>=0&&r<=length-1) { if(!same(pos[l],pos[r])) break; sum+=2; if(sum>max) { max=sum; from=l; to=r; } //比较函数应该在循环内进行,因为循环到这一步的时候,pos[ l ],pos[ r ]不应该是标点符号值 //切它们是相等的字符值,故sum+=2后马上进行判断处理 l--; r++; //判断完后,左编号继续做进,右编号仅需后进 while((pos[l]<'a'||pos[l]>'z')&&(pos[l]<'A'||pos[l]>'Z')&&l>=0) l--; while((pos[r]<'a'||pos[r]>'z')&&(pos[r]<'A'||pos[r]>'Z')&&r<=length-1) r++; } //当回文串为偶数的时候 l=i; r=i+1; sum=0; while(l>=0&&r<=length-1) { if(!same(pos[l],pos[r])) break; sum+=2; if(sum>max) { max=sum; from=l; to=r; } l--; r++; //比较完后,左编号前进一个,右编号后进一个 //前后进后,此时的pos[ l ],pos[ r ]不一定不是标点符号和空格 while((pos[l]<'a'||pos[l]>'z')&&(pos[l]<'A'||pos[l]>'Z')&&l>=0) l--; while((pos[r]<'a'||pos[r]>'z')&&(pos[r]<'A'||pos[r]>'Z')&&r<=length-1) r++; //忽略当前值为标点为标点符号或者为空格的情况 } } printf("%d\n",max); for(i=from;i<=to;i++) { printf("%c",pos[i]); if(cr[i]==1) printf("\n"); } if(cr[to]!=1) printf("\n"); //最终输出 return 0; }总结:
题意非常简单,但是实现方面却很棘手,没 有特别技巧的方法,只能这样子一一列举出来,需要更加细心,更加清晰每一步的操作有什么作用,会带来什么后果。考虑好数组边界问题,哪一步操作应先进行还是后进行。每一个点都要思考清楚才能着手。分析问题还是很容易就分析少了某几种特殊情况,还需继续努力啊。(注意这题的输入,每80个字符为一行,最终组成一个大的字符串数组)。
这题也存在有技巧性的地方:
比如测试奇数回文串的时候运用 l=r=i;sum=-1;这样赋值的话,数组的循环数就可以大胆地从0开始算起,并且如果第一项满足的话也是sum+=2,从而使sum=1,根据判断while(l>=0&&r<=length-1)来决定是否循环一下操作;
同理测试偶数回文串的时候运用l=i;r=i+1;sum=0。
相关推荐
Usaco中第一章中的一道题,挺有意思的。我的程序中间用到了折半查找,牺牲空间求效率
小牛工作室装备Calf Studio Gear是LINUX操作系统下用于LV2和JACK环境的音频插件包。 该套件包含许多效果(延迟,调制,信号处理,滤波器,均衡器,动态效果,失真和母带效果),乐器(SF2播放器,风琴模拟器和单音...
J2ME中文教程_calf1.01a(游戏制作),喜欢的童鞋可以下载看看
电化学和光谱法在中性pH条件下对Al(III)促进双链小牛胸腺DNA变性的研究,章福平,曹庆,本文主要研究了在悬汞电极上用微分脉冲伏安法、拉曼光谱以及圆二色光谱法研究双链小牛胸腺DNA(ds-DNA)与Al(III)之间的相互作用...
Dependence of surface-enhanced Raman scattering (SERS) from Calf thymus DNA on anions is investigated. With the silver colloid, the bands at 732, 960 and 1333 cm-1 for adenine (A), 1466 cm-1 for ...
Calf是一个简单的CGI应用程序,用于生成比您的Web服务器更凉爽的文件列表。 它按年和月组织文件,因为它主要用于浏览档案。 它需要一个特定的层次结构,即/YYYY/MM/something/file 。 例如/2014/01/pic/lipsum.jpg ...
比较两个数组,然后返回一个新数组,该数组的元素为两个给定数组中所有独有的数组元素。换言之,返回两个数组的差异。(6种解题方法) ... [1, "calf", 3, "piglet"], [1, "calf", 3, 4] 应该返回 ["piglet", 4]。
We used Raman spectroscopy to study the conformational changes of DNA induced by Cd2+ ions in different Cd2+ concentrations solution. The experimental results show that when the Cd^(2+)/PO^(-)_(2) ...
见下表: 总称雄性名称雌性名称小动物名称肉 chicken cock rooster hen chick chicken duck drake duck duckling goose gander goose gosling horse stallion mare foal cattle bull/ox cow calf beef pig boar sow ...
常见动物的英文名称horse马mare母马colt, foal马驹,小马pony矮马thoroughbred纯种马mustang野马mule骡ass, donkey驴ox牛buffalo水牛bull公牛cow母牛calf小牛,牛犊bullock, steer小阉牛heifer小母牛pig, swine猪boar...
giant salamander 娃娃鱼 C cat 猫 crab 螃蟹 camel 骆驼 cow 母牛 calf 小牛 cock 公鸡 chicken 小鸡 crocodile 鳄鱼 少儿动物英语单词全文共7页,当前为第2页。少儿动物英语单词全文共7页,当前为第2页。cricket ...
host.add_plugin ("http://calf.sourceforge.net/plugins/Compressor" ,"compressor" .to_owned (), std:: ptr::null_mut ()).expect ("Lv2hm: could not add plugin" ); host.add_plugin (...
In this paper, the interaction between mitoxantrone and calf thymus DNA is investigated by Raman and fluorescence spectroscopies, and the binding site of mitoxantrone to calf thymus DNA is explored....
RITA DSL 这是一种宽松地基于语言的语言,专注于编写手动语言规则,该规则可...lengths = {"short", "long", "calf-length", "knee-length"} fabric_types = {"soft", "airy", "crinkled"} fabrics = {"velour", "chi
Kudu小牛Kudu Calf 用于从父 Kudu 站点部署子站点文档查看执照项目治理这个项目在保护伞下。
Function_CalF1.py (F1函数的计算) 负样本影响问题 测试产生 '候选集'的过程中,发现虽然只用子集,但是一早上起来,数据量还是把硬盘给爆了,经测试,代码应该没有产生大问题。估计是负样本太多,过多的想预测没有...
#########扁平蝴蝶######### -fbfly是#########削片机######### -router.algorithm DR_FLIT_SWITCHED_CALF -edge_loop true -meshEjectTrial 2 meshEjectTrial是弹出端口的宽度。 #########VC缓冲######### -router...
java web开发应用.类似人人空间的设计,比较简单,有说说,日志,相册,站内信,留言,互相访问等功能.登录页面设计类似人人网,数据库采用Oracle.
一个海康摄像头驱动开发的上位机Demo,功能简洁,面向上位机海康摄像机开发
spring 开发核心,值得好好看看,开发核心。