题目描述给定一个包含若干单词的字典单词由小写字母组成长度111到666且不重复字典以一行六个大写字母X即XXXXXX结束。随后输入若干个待解乱的单词scrambled words\texttt{scrambled words}scrambled words同样以XXXXXX结束。对于每个待解乱单词要求找出字典中所有可以由该单词的字母重新排列而成的单词即字母异位词并按字典序输出。若没有匹配的单词则输出NOT A VALID WORD。每个查询结果后输出一行六个星号******。输入格式输入包含四部分字典每行一个单词以XXXXXX结束。若干待解乱单词每行一个以XXXXXX结束。所有单词均由小写字母组成长度111到666。字典中的单词不重复但不一定按字典序排列。输出格式对于每个待解乱单词输出一行NOT A VALID WORD若无匹配否则按字典序输出所有匹配的字典单词每行一个。无论是否有匹配最后输出一行六个星号******。样例输入tarp given score refund only trap work earn course pepper part XXXXXX resco nfudre aptr sett oresuc XXXXXX输出score ****** refund ****** tarp trap ****** NOT A VALID WORD ****** course ******题目分析本题是经典的“异位词查找”问题。字典大小最多100100100单词长度不超过666查询数量未知但通常不多。由于规模极小可以直接对每个查询遍历整个字典判断两个单词排序后的字符串是否相同。为了确保输出顺序字典序可以在读入字典后按原始单词排序。这样在匹配时按顺序输出即可。解题思路读入字典单词存入结构体数组每个结构体包含原始单词word和其排序后的字符串sorted将word的字母排序。按原始单词对结构体进行升序排序以保证输出时按字典序。对于每个查询单词将其字母排序得到target。遍历字典结构体数组若sorted target则输出word。若无匹配则输出NOT A VALID WORD。最后输出******。由于单词长度很短排序操作非常快。总复杂度O((DQ)⋅Llog⁡L)O((D Q) \cdot L \log L)O((DQ)⋅LlogL)其中D≤100D \le 100D≤100QQQ未知L≤6L \le 6L≤6完全可接受。复杂度分析预处理字典排序每个单词O(D⋅Llog⁡L)O(D \cdot L \log L)O(D⋅LlogL)整体排序O(Dlog⁡D)O(D \log D)O(DlogD)。每个查询排序查询单词O(Llog⁡L)O(L \log L)O(LlogL)遍历字典O(D)O(D)O(D)次比较字符串O(L)O(L)O(L)总O(Q⋅D⋅L)O(Q \cdot D \cdot L)O(Q⋅D⋅L)。空间复杂度O(D⋅L)O(D \cdot L)O(D⋅L)。代码实现// Word Amalgamation// UVa ID: 642// Verdict: Accepted// Submission Date: 2016-08-25// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structitem{string word,sorted;booloperator(constitemanother)const{returnwordanother.word;}};intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);vectoritemitems;string line;while(getline(cin,line),line.front()!X){string backupline;sort(line.begin(),line.end());items.push_back((item){backup,line});}sort(items.begin(),items.end());while(getline(cin,line),line.front()!X){sort(line.begin(),line.end());booloutputedfalse;for(autodata:items)if(data.sortedline){outputedtrue;coutdata.word\n;}if(!outputed)coutNOT A VALID WORD\n;cout******\n;}return0;}总结本题通过将单词按字母排序作为“特征串”将异位词匹配转化为字符串相等比较实现简单高效。由于数据规模很小直接遍历字典即可。注意输出格式每个查询结果后必须紧跟六个星号无论是否有匹配。该解法清晰直观是处理字母重排问题的常用技巧。