UVa 175 Keywords

题目分析本题要求根据给定的若干个兴趣配置文件Profile \texttt{Profile}Profile和标题Title \texttt{Title}Title判断每个标题是否被每个配置文件选中。选中的条件是在标题中存在至少一对来自配置文件的关键词它们之间的单词个数不超过配置文件给定的阈值。输入格式如下配置文件以P:开头后面依次为一个整数阈值和至少两个小写关键词。标题以T:开头后跟一个以|结尾的字符串。标题可能跨多行每行不超过80 8080个字符总长度不超过255 255255个字符。非字母字符被忽略大写字母转为小写。文件以一行#结束。输出格式为对于每个配置文件输出其编号和选中的标题编号编号从1 11开始标题编号按升序排列用逗号分隔。解题思路本题的核心是关键词匹配和距离判断。1. 输入处理读取每一行判断行首是否为P:或T:。若为P:解析阈值和关键词存入profiles和gaps数组。若为T:将多行内容拼接直到遇到|然后进行预处理保留字母和空格其他字符删除。大写字母转小写。按空格分词得到标题的单词列表。遇到#时停止输入。2. 匹配与距离判断对于一个配置文件i ii和一个标题j jj配置文件中可能包含多个关键词至少2 22个。我们需要判断是否存在一对关键词可以是不相邻的顺序如第一个和第三个它们在标题中的位置差即中间隔的单词数不超过阈值g a p gapgap。具体实现方法遍历标题中的每个单词如果匹配到配置文件中的第p pp个关键词则向后遍历配置文件中的其他关键词q qqq p q pqp。在标题中只检查距离当前单词前后g a p 1 gap 1gap1范围内的单词即最多间隔g a p gapgap个单词。如果找到匹配则返回true \texttt{true}true。3. 输出结果按配置文件顺序输出每个配置文件一行包含选中标题的编号。注意事项标题中的单词可能重复因此不能简单使用find \texttt{find}find。阈值表示中间最多可以有多少个单词因此搜索范围为[n - gap - 1, n gap 1]。行末的|是标题结束标志|本身不出现在标题内容中。输入中P和T后的冒号后面可能有空格需要处理。代码实现// Keywords// UVa ID: 175// Verdict: Accepted// Submission Date: 2016-02-21// UVa Run Time: 0.000s#includebits/stdc.husingnamespacestd;vectorvectorstringprofiles;// 存储每个配置文件的关键词列表vectorintgaps;// 存储每个配置文件的阈值vectorvectorstringtitles;// 存储每个标题的单词列表// 处理配置文件voidprocessProfile(string line){// 去掉开头的 P:lineline.substr(line.find(P:)2);string word;intdistance;istringstreamiss(line);issdistance;// 读取阈值gaps.push_back(distance);// 存入 gaps 数组vectorstringkeywords;while(issword)keywords.push_back(word);// 读取后续关键词profiles.push_back(keywords);// 存入 profiles 数组}// 处理标题voidprocessTitle(string line){// 去掉开头的 T:lineline.substr(line.find(T:)2);// 从后往前处理删除非字母字符并将大写字母转为小写for(intiline.length()-1;i0;i--)if(isalpha(line[i])){if(isupper(line[i]))line[i]tolower(line[i]);}elseif(line[i]! line[i]!\t)line.erase(line.begin()i);// 按空格分词istringstreamiss(line);vectorstringsingleTitle;string word;while(issword)singleTitle.push_back(word);titles.push_back(singleTitle);}// 判断第 i 个配置文件是否选中第 m 个标题boolfindKeywords(inti,intm,intgap){// 遍历配置文件中的每一对关键词for(intj0;jprofiles[i].size()-1;j)for(intn0;ntitles[m].size();n){// 在标题中找到匹配的第一个关键词if(titles[m][n]profiles[i][j]){// 遍历配置文件中后面的关键词for(intkj1;kprofiles[i].size();k){// 计算搜索范围[n - gap - 1, n gap 1]intupngap1;intdownn-gap-1;for(intxmax(down,0);xmin(up,(int)(titles[m].size())-1);x){if(xn)continue;// 跳过自身if(titles[m][x]profiles[i][k])returntrue;// 找到匹配}}}}returnfalse;}// 对所有标题进行匹配搜索并输出结果voidsearchTitle(){for(inti0;iprofiles.size();i){cout(i1): ;boolfirstPrintedfalse;for(intj0;jtitles.size();j)if(findKeywords(i,j,gaps[i])){if(firstPrintedfalse)firstPrintedtrue;elsecout,;cout(j1);}cout\n;}}intmain(){cin.tie(0);cout.sync_with_stdio(false);string line,title;boolprofileEndedfalse;// 标记是否已经遇到第一个标题while(getline(cin,line),line!#){// 尚未遇到标题且当前行是配置文件if(profileEndedfalseline.find(T:)line.npos){processProfile(line);continue;}elseprofileEndedtrue;// 开始处理标题// 拼接标题内容titleline;// 遇到 | 表示一个标题结束if(line.find(|)!line.npos){processTitle(title);title.clear();// 清空准备下一个标题}}searchTitle();return0;}总结本题主要考察字符串处理和子串匹配的变形应用。关键在于正确处理输入格式、单词边界以及距离判断的范围控制。实现时注意非字母字符的过滤和大小写转换。标题跨行拼接。距离判断的边界条件避免数组越界。