UVa 698 Index

题目描述给定一个索引词列表和若干行文本需要为每个在文本中出现的索引词生成索引条目内容包括该词出现的行号。行号从111开始编号。若一个词在连续多行出现则合并为范围如3-4。若同一词在词典中出现多次重复的索引词则输出同样多次。索引词由字母和数字组成长度不超过101010大小写不敏感输出时统一大写。每行文本中单词由非字母数字字符分隔。输入格式多个测试用例。每个测试用例以若干行索引词开始每行一个词以空行结束。然后若干行文本以空行结束。整个输入以另一个空行结束即最后一个测试用例后的空行。输出格式对于每个测试用例输出Case X:其中XXX为用例编号从111开始。然后对于每个在文本中出现的索引词若词典中有多个相同词则输出多次输出该词输出格式为词 行号列表每个行号列表用逗号和空格分隔连续行合并为范围。最后在每个用例后输出一个空行。样例输入empty character of for it An empty line has no characters in it at all (except for the end of line character). No word will have more than ten characters in it. The end of the cases will be followed by another empty line. It follows the empty line ending the text of the last case. Repeat A line A repeat of a word on a line does not result in a repeat of the line number in the index.输出Case 1 CHARACTER 2 EMPTY 1, 4 FOR 1 IT 1, 3-4 OF 2-3, 5 Case 2 A 1 LINE 1-2 REPEAT 1题目分析本题要求对文本中的单词进行索引。关键步骤读入索引词列表转为大写存入mapstring, int记录每个词在词典中出现的次数用于重复输出以及mapstring, vectorpairint,int存储每个词出现的行号区间。逐行读入文本对每行提取所有由字母和数字组成的单词忽略其他字符转为大写。若该词在词典中则记录行号若该行号与前一个记录的行号连续则扩展当前区间否则新建区间。输出时按字典序排序因此我们采用map自然排序字典序。解题思路读入索引词列表存入mapstring, int counter记录出现次数和mapstring, vectorpairint,int indexing记录行号区间。逐行读入文本对每行遍历字符提取单词字母或数字转为大写若在indexing中存在则记录行号。记录行号时若该词已有一个区间且当前行号等于区间末尾1 11则扩展区间否则新建区间。输出按indexing的键顺序字典序对每个词若其区间列表非空则输出该词和行号区间列表用逗号和空格分隔连续区间合并为a-b。若counter[word] 1则输出多次。复杂度分析设文本行数为RRR每行单词数WWW索引词数TTT。总复杂度O(R⋅W⋅log⁡T)O(R \cdot W \cdot \log T)O(R⋅W⋅logT)。代码实现// Index// UVa ID: 698// Verdict: Accepted// Submission Date: 2017-06-22// UVa Run Time: 0.040s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);mapstring,intcounter;mapstring,vectorpairint,intindexing;string line,word;intcases0;while(getline(cin,word)){counter.clear();indexing.clear();do{for(inti0;iword.length();i)word[i]toupper(word[i]);counter[word];if(counter[word]1)continue;indexing.insert(make_pair(word,vectorpairint,int()));}while(getline(cin,word),word.length()0);intlineNumbers1;while(getline(cin,line),line.length()0){intidx0;while(idxline.length()){if(isalpha(line[idx])||isdigit(line[idx])){string block;while(idxline.length()){if(isalpha(line[idx])||isdigit(line[idx]))blocktoupper(line[idx]);elsebreak;idx1;}if(indexing.find(block)!indexing.end()){if(indexing[block].size()0){indexing[block].push_back(make_pair(lineNumbers,lineNumbers));}else{if(lineNumbers!indexing[block].back().second){if(indexing[block].back().second1lineNumbers)indexing[block].back().second1;elseindexing[block].push_back(make_pair(lineNumbers,lineNumbers));}}}}elseidx1;}lineNumbers1;}coutCase cases\n;for(autoentry:indexing){if(entry.second.size()0)continue;for(inti0;icounter[entry.first];i){coutentry.first;boolfirsttrue;for(autop:entry.second){if(first)firstfalse;elsecout,;cout ;if(p.firstp.second)coutp.first;elsecoutp.first-p.second;}cout\n;}}cout\n;}return0;}总结本题通过扫描文本提取单词并利用区间合并技术记录行号范围最后按字典序输出索引。关键点包括正确提取单词字母数字序列。大小写不敏感统一转为大写。重复索引词需要输出多次。连续行号合并为范围。该解法是文本索引的经典实现适合作为字符串处理和映射容器的练习。