题目描述给定一个词汇表包含NNN个单词N1000N 1000N1000和若干个测试单词。对于每个测试单词要求从词汇表中找出所有由相同字母组成即互为字母异位词anagram的单词并按词汇表原始顺序输出。若不存在则输出相应信息。输入包含多组测试用例每组以单词END结束。输入格式第一行为一个整数TTT表示测试用例的数量。随后可能有一个空行。每组测试用例结构如下第一行为一个整数NNN表示词汇表中单词的数量。接下来NNN行每行一个单词全小写长度不超过202020。接下来若干行每行一个测试单词全小写直到遇到单独一行END表示该组测试结束。注意END不是测试单词而是结束标记。各组之间可能有一个空行。输出格式对于每个测试单词输出以下格式Anagrams for: test word 1) anagram1 2) anagram2 ...其中序号占333位右对齐。若没有找到任何异位词则输出Anagrams for: test word No anagrams for: test word每组测试用例的输出之间用一个空行分隔。样例输入1 8 atol lato microphotographics rata rola tara tola pies tola kola aatr photomicrographics END输出Anagrams for: tola 1) atol 2) lato 3) tola Anagrams for: kola No anagrams for: kola Anagrams for: aatr 1) rata 2) tara Anagrams for: photomicrographics 1) microphotographics题目分析异位词anagram\texttt{anagram}anagram是指由相同字母组成但顺序不同的单词。对于每个测试单词需要在词汇表中找出所有与其字母组成相同的单词。由于单词长度不超过202020可以先将词汇表中的每个单词按字母排序得到其“特征串”然后将测试单词也排序只要特征串相同即为异位词。若多个词汇单词特征串相同则按它们在词汇表中出现的顺序输出。解题思路读入测试用例数TTT。对于每组测试读入词汇表大小NNN。对于每个词汇单词将其原样存入数组words[i]并将其排序后的副本存入sorted[i]。循环读入测试单词若为END则跳出循环。对于每个测试单词word先输出标题行Anagrams for: word。将word排序得到sorted_word。遍历词汇表若sorted[i] sorted_word则按顺序输出并计数。若计数为000则输出No anagrams for: word。每组测试之间输出一个空行第一组之前不输出。复杂度分析预处理词汇表O(N⋅Llog⁡L)O(N \cdot L \log L)O(N⋅LlogL)其中LLL为单词最大长度≤20\le 20≤20。每个测试单词匹配O(N⋅L)O(N \cdot L)O(N⋅L)但排序已在预处理中完成比较为O(L)O(L)O(L)总复杂度O(T⋅N⋅L)O(T \cdot N \cdot L)O(T⋅N⋅L)N≤1000N \le 1000N≤1000TTT较小可接受。空间复杂度O(N⋅L)O(N \cdot L)O(N⋅L)。代码实现// Anagrams (II)// UVa ID: 630// Verdict: Accepted// Submission Date: 2016-08-16// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string words[1100],sorted[1100];intword_count0,cases0;cincases;for(intc1;ccases;c){if(c1)cout\n;cinword_count;for(inti0;iword_count;i){cinwords[i];sorted[i]words[i];sort(sorted[i].begin(),sorted[i].end());}string word,backup;while(cinword,word!END){backupword;sort(word.begin(),word.end());coutAnagrams for: backup\n;intcount1;for(inti0;iword_count;i)if(wordsorted[i]){coutsetw(3)rightcount;cout) words[i]\n;count;}if(count1)coutNo anagrams for: backup\n;}}return0;}总结本题通过将单词排序得到特征串快速判断异位词关系并利用词汇表的原始顺序输出结果。关键点在于使用sort对单词进行重排得到标准形式。遍历词汇表时按输入顺序查找匹配项保证了输出顺序。注意输出格式中序号占333位右对齐使用setw(3)实现。每两组数据间输出一个空行但第一组前不要额外空行。该解法简单高效适合作为字符串处理的入门练习。