UVa 789 Indexing

题目描述给定一段由大写字母组成的文本以及一个字符KEYKEYKEY。文本中的单词由空格分隔每个单词长度不超过808080单词不会跨行每行长度不超过808080。要求输出一个按字典序升序排列的索引列出所有以KEYKEYKEY开头的单词每个单词后跟它出现的所有行号行号从111开始编号。同一行中一个单词出现多次行号只应出现一次。输入格式输入第一行为一个字符KEYKEYKEY。随后若干行文本由大写字母和空格组成。文本可能包含标点符号如逗号、句号这些标点符号应被视为单词的一部分根据样例TEXT.中的句点被视为单词的一部分但输出中只显示TEXT。实际上题目描述中“words”可能仅指由字母组成的连续序列但输入可能包含标点。样例中KEY,的逗号被忽略TEXT.的句点被忽略因此需要去除单词首尾的非大写字母字符。输入以文件结束终止。输出格式按字典序升序输出所有以KEYKEYKEY开头的单词每行格式为单词后跟一个空格然后是该单词出现的所有行号行号之间用空格分隔。每个单词只输出一次。样例输入T CONSIDER SEVERAL LINES OF TEXT AND ONE CHARACTER CALLED KEY, SPECIFIED ON A LINE PRECEDING THE TEXT. THE WORDS IN THE TEXT ARE SEPARATED BY SINGLE SPACE. THERE ARE NO WORDS SPLITTED BETWEEN TWO LINES. WRITE A PROGRAM TO DISPLAY AN INDEX OF ALL WORDS WITHIN THE TEXT STARTING WITH THE KEY. THE INDEX MUST BE ALPHABETICALLY SORTED. EACH WORD IN THE INDEX MUST BE FOLLOWED BY THE LIST OF THE LINE NUMBERS IN WHICH IT APPEARS.样例输出TEXT 1 2 5 THE 2 5 6 7 THERE 3 TO 5 TWO 3题目分析文本中的单词由连续的大写字母序列构成但可能存在非字母字符如标点附着在单词首尾。处理时需去除单词首尾的非大写字母字符仅保留大写字母组成的核心单词。然后筛选出首字符等于KEYKEYKEY的单词记录其出现的行号去重。最后按字典序输出所有符合条件的单词及其行号集合。解题思路实现步骤确定如下步骤1\texttt{1}1. 读取KEYKEYKEY字符忽略后续换行。步骤2\texttt{2}2. 初始化行号计数器lineNumbers1\textit{lineNumbers} 1lineNumbers1。使用std::mapstring, setint indexing存储每个单词及其出现行号的集合。步骤3\texttt{3}3. 循环读取每一行文本。对于每行使用字符串流istringstream提取每个单词以空格分隔。对每个单词循环去除首部非大写字母字符再循环去除尾部非大写字母字符。若处理后的单词非空且首字符等于KEYKEYKEY则将该行号插入到该单词对应的集合中。步骤4\texttt{4}4. 处理完一行后行号加111。步骤5\texttt{5}5. 所有行读完后按字典序遍历indexing输出每个单词和其行号集合行号升序因set自动排序。该算法时间复杂度O(Llog⁡W)O(L \log W)O(LlogW)其中LLL为单词总数WWW为不同单词数空间复杂度O(W)O(W)O(W)满足输入规模。代码实现// Indexing// UVa ID: 789// Verdict: Accepted// Submission Date: 2017-06-11// UVa Run Time: 0.110s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);mapstring,setintindexing;charkey;cinkey;cin.ignore(1024,\n);string line,word;intlineNumbers1;while(getline(cin,line)){istringstreamiss(line);while(issword){while(word.length()0!isupper(word.front()))word.erase(word.begin());while(word.length()0!isupper(word.back()))word.pop_back();if(word.length()0word.front()key)indexing[word].insert(lineNumbers);}lineNumbers1;}for(autoentry:indexing){coutentry.first;for(autonumber:entry.second)cout number;cout\n;}return0;}总结本题通过使用std::map和std::set实现了单词到行号的映射并自动完成去重和排序。关键在于正确提取单词的核心部分去除前后非大写字母字符。输入可能包含标点但单词由大写字母组成标点不被视作单词的一部分但样例显示标点会被忽略因此去除首尾非大写字母即可。输出按字典序升序行号升序完全符合要求。该解法简洁高效适用于类似索引生成任务。