UVa 454 Anagrams
题目描述
题目要求找出给定短语列表中的所有互为变位词（anagram\texttt{anagram}anagram）的短语对。变位词忽略空格，仅考虑字母的重排。输出时每对短语按字典序排列，且短语对之间也按字典序排序。
输入格式
第一行一个整数NNN，表示测试用例的数量，后面跟一个空行。每个测试用例包含若干行（最多100100100行），每行一个短语（可能包含空格）。输入以空行结束。两个连续测试用例之间由一个空行分隔。
输出格式
对于每个测试用例，输出所有变位词对，每行格式为phrase1 = phrase2，其中phrase1和phrase2按字典序排列，且所有输出行也按字典序排列。若没有变位词对，则不输出任何行。两个连续测试用例的输出之间由一个空行分隔。
样例
输入
1 carthorse horse horse cart i do not know u ok i now donut orchestra输出
carthorse = horse cart carthorse = orchestra horse cart = orchestra i do not know u = ok i now donut题目分析
本题的核心是判断两个短语是否为变位词。变位词的定义是：忽略空格后，两个短语包含相同的字母，且每个字母出现的次数相同。
标准化表示
为了便于比较，可以将每个短语转换为一个标准化的字符串：
- 去除所有空格。
- 将剩余字符按字母顺序排序。
- 排序后的字符串作为该短语的“签名”。
若两个短语的签名相同，则它们互为变位词。
算法步骤
- 读取所有短语，存储原始字符串。
- 对于每个短语，生成其签名（去空格后排序）。
- 将所有短语按原始字符串字典序排序。
- 枚举所有短语对(i,j)(i, j)(i,j)（i<ji < ji<j），若签名相同，则输出
words[i] = words[j]。 - 由于原始字符串已排序，且i<ji < ji<j，输出自然满足字典序要求。
注意点
- 输入中的空行表示测试用例结束，需要正确处理。
- 短语可能包含多个空格，需要全部去除。
- 输出时两个短语之间用
=分隔（空格-等号-空格）。
复杂度分析
设短语数量为MMM（M≤100M \le 100M≤100），每个短语长度不超过若干字符。排序复杂度O(MlogM)O(M \log M)O(MlogM)，枚举对O(M2)O(M^2)O(M2)，完全可接受。
代码实现
// Anagrams// UVa ID: 454// Verdict: Accepted// Submission Date: 2016-07-17// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string line;getline(cin,line);intcases=stoi(line);getline(cin,line);for(inti=1;i<=cases;i++){if(i>1)cout<<endl;vector<string>words;map<string,string>sorted;while(getline(cin,line),line.length()>0){words.push_back(line);for(inti=line.length()-1;i>=0;i--)if(isblank(line[i]))line.erase(line.begin()+i);sort(line.begin(),line.end());sorted[words.back()]=line;}sort(words.begin(),words.end());for(inti=0;i<words.size();i++)for(intj=i+1;j<words.size();j++)if(sorted[words[i]]==sorted[words[j]])cout<<words[i]<<" = "<<words[j]<<'\n';}return0;}