一道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:
我的思路是先讀入字典中的字符串,存起來.然后再讀入用來檢查的字符串,存起來.然后,將字典中的字符串和用來檢查的字符串分別按字母排序后形成新的字符串.然后根據(jù)新形成的用來檢查的字符串一個一個地與新形成的字典中的字符串比較,若相同則保存,不相同則忽略.
最后將比較后相同的字符串用一個冒泡排序進(jìn)行排序.然后按題目要求輸出.
輸出格式?jīng)]有問題,但是超時,誰知道應(yīng)該在哪個地方進(jìn)行優(yōu)化啊?