1.描述：
Most crossword puzzle fans are used to anagrams–groups of words with the same letters in different orders–for example OPTS, SPOT, STOP, POTS and POST. Some words however do not have this attribute, no matter how you rearrange their letters, you cannot form another word. Such words are called ananagrams, an example is QUIZ.
大多数纵横字谜迷都习惯于拼字游戏 —— 一组字母顺序不同的单词，例如OPTS、SPOT、STOP、POTS和POST。然而，有些单词没有这个属性，无论你如何重新排列它们的字母，你都无法形成另一个单词。这样的单词被称为ananagrams，例如QUIZ。
Obviously such definitions depend on the domain within which we are working; you might think that ATHENE is an ananagram, whereas any chemist would quickly produce ETHANE. One possible domain would be the entire English language, but this could lead to some problems. One could restrict the domain to, say, Music, in which case SCALE becomes a relative ananagram (LACES is not in the same domain) but NOTE is not since it can produce TONE.
显然，这些定义取决于我们工作的领域；你可能会认为ATHENE是一种ananagram，而任何化学家都会很快产生 ETHANE(乙烷)。一个可能的领域是整个英语，但这可能会导致一些问题。你可以把领域限制在音乐，在这种情况下，SCALE变成了一个相对的ananagram（LACES(鞋带)不在同一个域中），但音符(note)并不是因为它能产生音调(tone)。
Write a program that will read in the dictionary of a restricted domain and determine the relative ananagrams. Note that single letter words are, ipso facto, relative ananagrams since they cannot be ``rearranged’’ at all. The dictionary will contain no more than 1000 words.
编写一个程序，读入相关领域的字典，并确定相关的ananagrams。请注意，单字母单词实际上是相对的ananagrams，因为它们根本无法“重新排列”。这本词典最多可收录1000个单词。
2. 输入：
Input will consist of a series of lines. No line will be more than 80 characters long, but may contain any number of words. Words consist of up to 20 upper and/or lower case letters, and will not be broken across lines. Spaces may appear freely around words, and at least one space separates multiple words on the same line. Note that words that contain the same letters but of differing case are considered to be anagrams of each other, thus tIeD and EdiT are anagrams. The file will be terminated by a line consisting of a single #.
3.输出：
Output will consist of a series of lines. Each line will consist of a single word that is a relative ananagram in the input dictionary. Words must be output in lexicographic (case-sensitive) order. There will always be at least one relative ananagram.
4.样例输入：
ladder came tape soon leader acme RIDE lone Dreis peat ScAlE orb eye Rides dealer NotE derail LaCeS drIed noel dire Disk mace Rob dries #
5.样例输出：
Disk NotE derail drIed eye ladder soon
6.题目大意：
给出字典领域，找出所有相对的ananagram，以区分大小写的字典序输出
7.思路
所有的单词最后没有被处理(没有被转换大小写)，所以我们要用一个vector存储一下所有单词，怎么检查是不是相对的ananagram呢，如果两个单词组成相同，那么他们全部字母小写/大写之后排字典序的单词一定相同，把所有单词存进map，最后按vector里的顺序检查存入个数是否超过二即可;
8.代码
#include<bits/stdc++.h> using namespace std; map<string,int>mp; string ss; vector<string>ve; set<string>st; bool judge(string ss) { for(int i=0;i<ss.size();i++) { ss[i]=tolower(ss[i]); } sort(ss.begin(),ss.end()); if(mp[ss]>1) return 1; else return 0;//当存入个数只有1时视为ananagram } int main() { while(cin>>ss) { if(ss=="#") break; if(ss.size()==1) { st.insert(ss); continue; }//单字母单词直接存入 ve.push_back(ss);//在vector中存入单词 for(int i=0;i<ss.size();i++) { ss[i]=tolower(ss[i]); }//小写处理 sort(ss.begin(),ss.end());//排序 mp[ss]++;//计数 } for(int i=0;i<ve.size();i++) { if(judge(ve[i])==0)//判断合法存入set { st.insert(ve[i]); } } for(auto k : st) { cout<<k<<endl; } }
9.反思
一开始我判断是否是ananagram的方法是先存储，小写，计数，没排序，去查找所有单词的全排列是否在计数中出现，虽然全排列函数时间复杂度很低，但是遇到长单词时根本无法处理，一个长度为 n 单词的全排列 有 n！个，遇到稍微长的单词时间复杂度就爆了，所以正确的处理方法是小写后做一次排序，所有相同组成单词的排序都是相同的；
故 判断两个单词是否是相同组成(不区分大小写) 的办法就是全部字母小写排序看是否相同
