博客

紫书刷题进行中，题解系列【

GitHub

|

CSDN

】

习题5-10 UVA1597 Searching the Web（65行AC代码）

题目大意

给定若干篇有编号的文章，构造一个搜索引擎，处理查询命令。

搜索引擎构造

原题描述中的

Figure-1

说得很清楚，即对于每个单词，将它出现的地方以**（文章编号，行号）**形式记录。

同时题目对问题做了简化：

• 每个单词仅包含26个字母，其余字符（包括
  
  数字，连字符
  
  ）均可看成空格
• 不考虑时态问题，大小不敏感（全转为小写）

命令格式

输出时均按输入文章时的顺序，注意单词所在文章和行的区别

• 
term

  ：直接输出term所在行
• 
term1 AND term2

  ：求两个单词所在
  
  文章交集
  
  ，将
  
  交集文章中对应的行全部输出
  
• 
term OR term

  ：求两个单词所在
  
  行的并集
  
• 
NOT term

  ：将不包含单词的文章
  
  整篇输出
  

算法设计

定义如下数据结构分别存储

每个单词对应的文章id和行号

，

每篇文章的每一行

map<string, vector<pair<int,int> > > mp; // 单词->(文章id,行号)
vector<string> doc[110]; // 文本

在读入每行字符串时，将非26字母表中的字符全部转为空格，然后用

stringstream

分割得到每个单词对应位置，较容易完成搜索引擎构造。

对于

与或非

命令可用

集合交并补

方式处理，比较简单

注意点

• 按文章输入顺序输出相应行/文章
• 不同文章的句子需10个
  
-

  分隔
• 在遍历
  
set/map

  过程中，不要进行删除操作，否则会
  
RE

• 提取不同命令的共性，简化代码
• 先写结构，再逐步细化，瀑布式开发，写一点测试一点

AC代码（C++11，字符串处理，map）

#include<bits/stdc++.h>
using namespace std;
int N, M;
string s, st, t1, t2;
map<string, vector<pair<int,int> > > mp; // 单词->(文章id,行号)
vector<string> doc[110]; // 文本
int main() {
    cin >>N; getchar(); // 吸收换行
    for (int i = 0; i < N; i ++) { // 所有文本 
        int line=0; // 行号
        while (getline(cin ,s) && s[0] != '*') {
            doc[i].push_back(s); // 文本i的第line行
            for (auto& ch : s) 
                if (!isalpha(ch)) ch = ' '; // 非字母全换为空格
                else ch = tolower(ch); // 字母均转为小写
            stringstream input(s); // 空格分割
            while (input >>s) mp[s].push_back({i, line}); // word所在文本编号和行号
            line ++; // 行号增加
        }
    }
    cin >>M; getchar();
    while (M --) { // 查询处理
        getline(cin, s); // 查询
        int i = s.find(' '), j = s.rfind(' '); // 从首，尾开始遇见的第一个空格位置
        set<pair<int,int> > out; // 输出集合
        if (i == string::npos) out.insert(mp[s].begin(), mp[s].end());  // term
        else { // 与或非
            if (s[0] == 'N') { // NOT
                t1 = s.substr(i+1);
                set<int> _set;
                for (int i = 0; i < N; i ++) _set.insert(i); // 所有文章id
                for (auto p : mp[t1]) _set.erase(p.first); // 删除包含t1的文章id
                for (auto p : _set) { // 输出整篇文章
                    for (auto line : doc[p]) cout <<line <<endl; // 打印不包含t1的所有整篇文章
                    if (p != *_set.rbegin()) cout <<"----------"<<endl; // 不同文章需间隔
                }
                if (_set.empty()) cout <<"Sorry, I found nothing.\n"; // 空处理
            }
            else { // AND,OR
                t1 = s.substr(0, i); // term1
                t2 = s.substr(j+1); // term2
                out.insert(mp[t1].begin(), mp[t1].end()); // 求并集 
                out.insert(mp[t2].begin(), mp[t2].end());
                if (j - i - 1 == 3) { // AND，求交集
                    set<int> set1, set2;
                    for (auto p : mp[t1]) set1.insert(p.first); // t1所在文本
                    for (auto p : mp[t2]) if (set1.find(p.first) != set1.end()) set2.insert(p.first); // 求交集文本
                    auto tmp = out; // 先备份，再删除；若边删边遍历会RE
                    for (auto p : tmp) if (set2.find(p.first) == set2.end()) out.erase(p); // 删除不相交的
                }
            }
        }
        int pre=-1; // 控制间隔输出
        if (s[0] != 'N') { // 非NOT语句统一输出
            for (auto p : out) {
                if (pre != -1 && pre != p.first) cout <<"----------"<<endl; // 两个不同文章之间
                pre = p.first;
                cout <<doc[p.first][p.second] <<endl;
            }
            if (out.empty()) cout <<"Sorry, I found nothing.\n";
        }
        cout <<"==========" <<endl;
    }
    return 0;
}