uva 156 – Ananagrams

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=92
题意:给出一段文字,包含若干个单词,以’#’结束。按照字典序输出所有的ananagrams。所谓ananagram,是指经过任意的重排后,不能得到这段文字中的另一个单词(不区分大小写)
思路:首先是字符串的读入…可以整行读入然后用空格分隔单词。由于补区分大小写,所以要都转化成小写…但是输出的时候要输出原始,所以还记得保留一份。而且要能够通过新的找到原始的(我用了一个toori的map<string,string>来实现)
然后最关键的部分是如何判断两个单词经过重排是否能一样…

我的做法是构造一个hash函数…一个单词的hash值等于对应字母的顺序的平方和…效果还不错?

单词和hash值一一对应…最大也就9E5,可以存的下。然后统计每个hash值出现的次数。对于那些只出现一次的,就是我们要的答案。

还要注意的是输出要按照原始单词的字典序,而不是都变成小写以后的字典序。

所以找到之后可以先找到对应的原始单词存到set里,最后再输出。

 

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz