一道ACM题目5036 Match WordsTimeLimit : 1 Second Memorylimit : 32 Megabyte Totalsubmit : 273 Accepted : 49xiaoz 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 tha

一道ACM题目5036 Match WordsTimeLimit : 1 Second Memorylimit : 32 Megabyte Totalsubmit : 273 Accepted : 49xiaoz 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 tha
一道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:
我的思路是先读入字典中的字符串,存起来.然后再读入用来检查的字符串,存起来.然后,将字典中的字符串和用来检查的字符串分别按字母排序后形成新的字符串.然后根据新形成的用来检查的字符串一个一个地与新形成的字典中的字符串比较,若相同则保存,不相同则忽略.
最后将比较后相同的字符串用一个冒泡排序进行排序.然后按题目要求输出.
输出格式没有问题,但是超时,谁知道应该在哪个地方进行优化啊?

一道ACM题目5036 Match WordsTimeLimit : 1 Second Memorylimit : 32 Megabyte Totalsubmit : 273 Accepted : 49xiaoz 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 tha
哈工程上的题目?
做的时间有点长了,忘记了,不过代码还在.
#include
using 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);
if( t ) return t < 0;
return strcmp (x.pa,y.pa) < 0;
}
int search(char *s)
{
int left = 0,right = n-1,mid;
while( left 0) left = mid + 1;
else right = mid - 1;
}
return -1;
}
int main()
{
int i = 0;;
while(scanf( "%s",a[i]) ,a[i][0] != '#')
{
strcpy(b[i],a[i]);
sort(b[i],b[i]+strlen(b[i]));
c[i].pa = a[i];
c[i].pb = b[i];
i++;
}
n = i;
sort(c,c+n,cmp);
char s[31];
while(scanf("%s",s),s[0] != '#')
{
printf("%s:",s);
sort(s,s+strlen(s));
int t = search(s);
if( t == -1 )
{
putchar('\n');
continue;
}
putchar(' ');
while(t>0 && strcmp(c[t-1].pb,c[t].pb) == 0 ) t--;
do
{
printf("%s ",c[t].pa);
t++;
}while(t