题目
一道ACM题目
5036 Match WordsTimeLimit : 1 Second Memorylimit : 32 Megabyte
Totalsubmit : 273 Accepted : 49
xiaoz wants to remember more words.So he asks you ,as a member of a development team for a words-matching program,
to write a module that will check if a given word can match some words of a known dictionary. The dictionary is
made of words.A word w matchs a word v if and only if there is some permutation p of character positions that
takes w to v.For example,"caret" can match "cater",but "caret" can't match "certe".
Input
The first part of the input contains all words from the dictionary. Each word occupies its own line. This part is
finished by the single character '#' on a separate line. All words are different. There will be at most 20000 words
in the dictionary.
The next part of the file contains all words that are to be checked. Each word occupies its own line. This part is
also finished by the single character '#' on a separate line. There will be at most 2000 words that are to be checked.
All words in the input (words from the dictionary and words to be checked) consist only of small alphabetic characters
and each one contains 30 characters at most.
Output
Write to the output exactly one line for every checked word in the order of their appearance in the second part of the
input file.Write the checked word first,then write the character ':',and after a signle space write all its possible
words ,from the dictionary,which can match the checked word.The matching words should be written in alphabetical order.
If there are no matching words for the checked word then the line feed should immediately follow the colon.
Sample Input
undisplayed
trace
tea
singleton
eta
eat
displayed
crate
cater
carte
caret
beta
beat
bate
ate
abet
#
retac
btae
good
displayde
hello
#
Sample Output
retac: caret carte cater crate trace .
btae: abet bate beat beta .
good:
displayde:displayed .
hello:
我的思路是先读入字典中的字符串,存起来.然后再读入用来检查的字符串,存起来.然后,将字典中的字符串和用来检查的字符串分别按字母排序后形成新的字符串.然后根据新形成的用来检查的字符串一个一个地与新形成的字典中的字符串比较,若相同则保存,不相同则忽略.
最后将比较后相同的字符串用一个冒泡排序进行排序.然后按题目要求输出.
输出格式没有问题,但是超时,谁知道应该在哪个地方进行优化啊?
5036 Match WordsTimeLimit : 1 Second Memorylimit : 32 Megabyte
Totalsubmit : 273 Accepted : 49
xiaoz wants to remember more words.So he asks you ,as a member of a development team for a words-matching program,
to write a module that will check if a given word can match some words of a known dictionary. The dictionary is
made of words.A word w matchs a word v if and only if there is some permutation p of character positions that
takes w to v.For example,"caret" can match "cater",but "caret" can't match "certe".
Input
The first part of the input contains all words from the dictionary. Each word occupies its own line. This part is
finished by the single character '#' on a separate line. All words are different. There will be at most 20000 words
in the dictionary.
The next part of the file contains all words that are to be checked. Each word occupies its own line. This part is
also finished by the single character '#' on a separate line. There will be at most 2000 words that are to be checked.
All words in the input (words from the dictionary and words to be checked) consist only of small alphabetic characters
and each one contains 30 characters at most.
Output
Write to the output exactly one line for every checked word in the order of their appearance in the second part of the
input file.Write the checked word first,then write the character ':',and after a signle space write all its possible
words ,from the dictionary,which can match the checked word.The matching words should be written in alphabetical order.
If there are no matching words for the checked word then the line feed should immediately follow the colon.
Sample Input
undisplayed
trace
tea
singleton
eta
eat
displayed
crate
cater
carte
caret
beta
beat
bate
ate
abet
#
retac
btae
good
displayde
hello
#
Sample Output
retac: caret carte cater crate trace .
btae: abet bate beat beta .
good:
displayde:displayed .
hello:
我的思路是先读入字典中的字符串,存起来.然后再读入用来检查的字符串,存起来.然后,将字典中的字符串和用来检查的字符串分别按字母排序后形成新的字符串.然后根据新形成的用来检查的字符串一个一个地与新形成的字典中的字符串比较,若相同则保存,不相同则忽略.
最后将比较后相同的字符串用一个冒泡排序进行排序.然后按题目要求输出.
输出格式没有问题,但是超时,谁知道应该在哪个地方进行优化啊?
提问时间:2021-04-01
答案
哈工程上的题目?做的时间有点长了,忘记了,不过代码还在.#includeusing namespace std;char a[20002][31],b[20002][31];int n;struct Node{char *pa,*pb;}c[20002];bool cmp(Node x,Node y){int t = strcmp(x.pb,y.pb...
举一反三
已知函数f(x)=x,g(x)=alnx,a∈R.若曲线y=f(x)与曲线y=g(x)相交,且在交点处有相同的切线,求a的值和该切线方程.
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
奥巴马演讲不用看稿子.为什么中国领导演讲要看?
想找英语初三上学期的首字母填空练习……
英语翻译
最新试题
- 1work on the office的意思
- 2三个人去住宿,房价是30.一人出了10块.但今天优惠只要25块,老板给了服务员5块叫他退回去,他自己拿了2块
- 3英语翻译
- 4TSSOP封装和SOP封装有什么区别
- 5小明按顺序做题,还没做完的题目比已做完的题目多2分之1,已知共有40道题,小明正在做第几题?
- 6一元二次方程x^2-2mx+m+2=0(x>0)有两个实根,求两个实根平方和的取值范围
- 7某铁路桥长1750m,现有一列火车从桥上通过,测得该火车从开始上桥到完全过桥共用了80s,整列火车完全在桥上的时间共60s;设火车的速度为xm/s,火车的长度为ym,根据题意列方程组为_.
- 8What do you_____ after school?这个空填doing,为什么?为什么不填do?
- 9作革兰氏染色涂片为什么不能过于浓厚?其染色成败的关键是什么?
- 10等式与不等式基本性质的区别
热门考点
- 1利用光学显微镜观察细胞的失水时发现,植物细胞不如动物细胞收缩得那么显著,原因是( ) A.动、植物细胞膜的伸缩性不同 B.植物细胞有细胞壁 C.动物细胞质浓度大于植物细胞液的浓
- 2一个木盆的底面是圆形,在它的底部箍一根长2.552米的铁丝,铁丝的接头处用了0.04米,这个木盆的底面半径是
- 3修路,有甲乙两个工程队,若两队合作需24天完成,费用120万元,若甲队单独做20天后剩下的由乙队做,
- 4氯气制备原理的离子方程式?
- 5内角的度数为整数的正n边形的个数是( ) A.24 B.22 C.20 D.18
- 6已知5x|2a+1|与4x(b—3)的平方互为相反数,代数式a的b次方+2a的2007次方为多少?
- 7他们有物美价廉的帽子.They have hats 后面有五个空~
- 8如果已知A=5x²+7x+1 ,B=x²-9x+15,求x的值,使得A=B
- 9求自我介绍类型的小作文.新学期开学用的.
- 10请问乙醇在发生化学反应时,化学键断裂的顺序是什么?