题目描述

题目要求找出给定短语列表中的所有互为变位词（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

题目分析

本题的核心是判断两个短语是否为变位词。变位词的定义是：忽略空格后，两个短语包含相同的字母，且每个字母出现的次数相同。

标准化表示

为了便于比较，可以将每个短语转换为一个标准化的字符串：

1. 去除所有空格。
2. 将剩余字符按字母顺序排序。
3. 排序后的字符串作为该短语的“签名”。

若两个短语的签名相同，则它们互为变位词。

算法步骤

1. 读取所有短语，存储原始字符串。
2. 对于每个短语，生成其签名（去空格后排序）。
3. 将所有短语按原始字符串字典序排序。
4. 枚举所有短语对(i,j)(i, j)(i,j)（i<ji < ji<j），若签名相同，则输出words[i] = words[j]。
5. 由于原始字符串已排序，且i<ji < ji<j，输出自然满足字典序要求。

注意点

• 输入中的空行表示测试用例结束，需要正确处理。
• 短语可能包含多个空格，需要全部去除。
• 输出时两个短语之间用=分隔（空格-等号-空格）。

复杂度分析

设短语数量为MMM（M≤100M \le 100M≤100），每个短语长度不超过若干字符。排序复杂度O(Mlog⁡M)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;}