UVa 642 Word Amalgamation-育师

题目描述

给定一个包含若干单词的字典（单词由小写字母组成，长度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((D+Q)⋅Llog⁡L)O((D + Q) \cdot L \log L)O((D+Q)⋅LlogL)，其中D≤100D \le 100D≤100，QQQ未知，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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;structitem{string word,sorted;booloperator<(constitem&another)const{returnword<another.word;}};intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);vector<item>items;string line;while(getline(cin,line),line.front()!='X'){string backup=line;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());booloutputed=false;for(autodata:items)if(data.sorted==line){outputed=true;cout<<data.word<<'\n';}if(!outputed)cout<<"NOT A VALID WORD\n";cout<<"******\n";}return0;}