UVa 1597 - Searching the Web（模拟）

发表于 | 分类于 ， |

模拟网页搜索，直接遍历查找会超时，需要使用映射或指针一类的简化查找。
直接用STL写的，原本准备超时之后再用指针重写，没想到2.595s过了，就懒得改了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<sstream>
#include<vector>
#include<set>
#include<map>
using namespace std;
struct inc{
    set<int> doc,line[110];
};
map<string,inc> dict;
vector<string> a[110];
void pre(string s,int a,int l){
    for(int i=0;i<s.length();++i)
        if(isalpha(s[i])) s[i]=tolower(s[i]);
        else s[i]=' ';
    stringstream ss(s);
    while(ss>>s){
        if(!dict.count(s)) dict[s]=inc();
        dict[s].doc.insert(a);
        dict[s].line[a].insert(l);
    }
    return;
}
int main(){
    ios::sync_with_stdio(false);
    //freopen("in_1.txt","w",stdout);
    int n,m,cnt;
    cin>>n;cin.get();
    for(int i=0;i<n;++i){
        cnt=0;
        string s;
        while(getline(cin,s),s!="**********"){
            pre(s,i,cnt++);
            a[i].push_back(s);
        }
    }
    cin>>m;cin.get();
    for(int i=0;i<m;++i){
        bool flag=true;
        string s;
        getline(cin,s);
        if(s.find(" AND ")!=s.npos){
            stringstream ss(s);
            string s1,s2;
            ss>>s1>>s2>>s2;
            for(int i=0;i<n;++i){
                if(dict[s1].doc.count(i)&&dict[s2].doc.count(i)){
                    if(flag) flag=false;
                    else cout<<"----------\n";
                    set<int> k;
                    for(set<int>::iterator it=dict[s1].line[i].begin();it!=dict[s1].line[i].end();++it)
                        k.insert(*it);
                    for(set<int>::iterator it=dict[s2].line[i].begin();it!=dict[s2].line[i].end();++it)
                        k.insert(*it);
                    for(set<int>::iterator it=k.begin();it!=k.end();++it)
                        cout<<a[i][*it]<<endl;
                }
            }
        }
        else if(s.find(" OR ")!=s.npos){
            stringstream ss(s);
            string s1,s2;
            ss>>s1>>s2>>s2;
            for(int i=0;i<n;++i){
                if(dict[s1].doc.count(i)||dict[s2].doc.count(i)){
                    if(flag) flag=false;
                    else cout<<"----------\n";
                    set<int> k;
                    for(set<int>::iterator it=dict[s1].line[i].begin();it!=dict[s1].line[i].end();++it)
                        k.insert(*it);
                    for(set<int>::iterator it=dict[s2].line[i].begin();it!=dict[s2].line[i].end();++it)
                        k.insert(*it);
                    for(set<int>::iterator it=k.begin();it!=k.end();++it)
                        cout<<a[i][*it]<<endl;
                }
            }
        }
        else if(s.find("NOT ")!=s.npos){
            string s0=s.substr(4);
            for(int i=0;i<n;++i){
                if(!dict[s0].doc.count(i)){
                    if(flag) flag=false;
                    else cout<<"----------\n";
                    for(int j=0;j<a[i].size();++j)
                        cout<<a[i][j]<<endl;
                }
            }
        }
        else{
            for(int i=0;i<n;++i){
                if(dict[s].doc.count(i)){
                    if(flag) flag=false;
                    else cout<<"----------\n";
                    for(set<int>::iterator it=dict[s].line[i].begin();it!=dict[s].line[i].end();++it)
                        cout<<a[i][*it]<<endl;
                }
            }
        }
        if(flag) cout<<"Sorry, I found nothing.\n";
        cout<<"==========\n";
    }
    return 0;
}

本文迁移自我的 CSDN博客 ，格式可能有所偏差。