UVA156 反片语 Ananagrams

此题可以在洛谷上刷！[UVA156 反片语 Ananagrams]

Description
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.
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.
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.
Input
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 ‘#’.
Output
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.
Sample Input

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
#

Sample Output

Disk
NotE
derail
drIed
eye
ladder
soon

题意翻译
题目大意输入一些单词，找出所有满足如下条件的单词：该单词不能通过字母重排，得到输入文本的另外一个单词。在判断是否满足条件时，字母不分大小写，但在输出时应保留输入的大小写，按字典序排列。翻译贡献者：很dalao的蒟蒻

题目大致思路

数据量不大，可以随心浪，n2也不怕，快排n次跑。

先不停的输入字符串，检测#退出，然后把原始的字符串记录在一个数组里面，保留原始数据。

问题是怎么判断出现过没有。这里需要将每一个字符串中的每一个字符都按照字典序排序（统一）！然后将其加入到一个映射表（map）里，出现一次将映射变量加一。

最后用一个ans数组记录结果，首先按照字典序排序原始数据数组，然后遍历原始数据，判断重排后的元素在映射表中是否只出现一次，是将元素加入，否不记录。

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
//#include <windows.h>
using namespace std;
//DWORD starttime, endtime, sumtime;
map<string, int>cnt;//这里的string是单词，int是出现了几次。
vector<string>words;//把所有单词全部压入动态数组
string strs[10001];
string repr(const string& s) { 
    string ans = s;//由于是&（不引用还要再复制一个），所以不能随意乱改字符串（尤其是const）
    for (int i = 0; i < ans.length(); i++) { 
        ans[i] = tolower(ans[i]);//把大写字母变成小写字母
    }
    sort(ans.begin(), ans.end());//快速排序
    return ans;
}//此函数将单词标准化，全部转成小写字母再排序。
int main()
{ 
    int n = 0;
    string s;
    while (cin >> s) { 
        //starttime = GetTickCount();
        if (s[0] == '#')break; // 跳出条件
        words.push_back(s); //储存单词
        string r = repr(s);
        if (!cnt.count(r))cnt[r] = 0;
        //如果这个单词还没有出现过，就把个数存为0
        cnt[r]++; //不管怎样都要将数值加1
        //endtime = GetTickCount();
        //sumtime += (endtime - starttime);
    }//本循环将原单词存入words中，把标准化的单词存入cnt中
    //starttime = GetTickCount();
    vector<string>ans; //答案
    for (int i = 0; i < words.size(); i++) { 
        if (cnt[repr(words[i])] == 1)ans.push_back(words[i]);
    } //本循环将只出现一次的标准化单词存入ans中
    sort(ans.begin(), ans.end());//快速排序，按照字典序最后处理
    for (int i = 0; i < ans.size(); i++) { 
        cout << ans[i] << endl;
    }
    //endtime = GetTickCount();
    //sumtime += (endtime - starttime);
    //cout << "USED:" << sumtime << "ms" << endl; // 经过测速，发现此算法针对此题是很快的
    return 0;
}