【UVA-1597】Searching the Web【字符串拆分+STL的简单应用】

【UVA-1597】Searching the Web【字符串拆分+STL的简单应用】

问题链接:https://vjudge.net/problem/UVA-1597

Solution:

由于输出要求大多是按照行为单位的,所以我们使用vector来记录行,并且记录清楚行号、文章号,之后将每个句子中的单词转化成小写字母,之后拆分出来,存到一个map中,map的值是一个集合,表示这个单词出现在对应的vector中的哪些句子记录中。拆分函数cutstr()十分关键。

#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <sstream>
#include <cctype>
#define DBG

using namespace std;

struct Centence {
    string str;
    int idx;
    int pos;
};

vector<Centence> datas;
struct cmp {
    bool operator()(const int a, const int b) const {
        if (datas[a].idx != datas[b].idx) return datas[a].idx < datas[b].idx;
        else if (datas[a].pos != datas[b].pos) return datas[a].pos < datas[b].pos;
        return a < b;
    }
};

inline void tolow(string &str) {
    for (int i = 0; i < str.size(); i++)
        if (isalpha(str[i])) str[i] = tolower(str[i]);
}
string in, out;
int cut_i;
inline bool cutstr(const string s) {
    if (s != "") in = s, cut_i = 0;
    if (cut_i == in.size()) return false;
    out = "";
    for (int cnt = 0; cut_i < in.size() && cnt < 2; cut_i++) {
        if (cnt == 0 && isalpha(in[cut_i])) cnt = 1;
        else if (cnt == 1 && !isalpha(in[cut_i])) cnt = 2;
        if (cnt == 1) out += in[cut_i];
    }
    if (out == "") return false;
    else return true;
}

map<string, set<int, cmp> > wordIdx;

int main(void) {
    ios::sync_with_stdio(false);
    // cin.tie(NULL);
    int n, m;
    cin >> n;
    string tmp, t;
    Centence c;
    int cnt = 0;
    getline(cin, tmp);
    for (int i = 0; cnt < n; i++) {
        getline(cin, tmp);
        if (tmp == "**********") {
            cnt++;
            i--;
            continue;
        }
        c.str = tmp, c.idx = cnt, c.pos = i;
        datas.push_back(c);
        stringstream ss;
        ss << tmp;
        while (ss >> t) {
            tolow(t);
            cutstr(t);
            do {
                if (!wordIdx.count(out)) wordIdx[out] = set<int, cmp>();
                wordIdx[out].insert(datas.size() - 1);
            } while (cutstr(""));
        }
    }
    cin >> m;
    string str;
    getline(cin, str);
    bool flag = true;
    while (m--) {
        getline(cin, str);
        stringstream ss;
        ss << str;
        t = "";
        ss >> tmp >> t;
        flag = true;
        if (t == "AND") {
            ss >> t;
            tolow(tmp), tolow(t);
            set<int, cmp> sa, sb, sc;
            sa = wordIdx[tmp], sb = wordIdx[t];
            for (int x : sa)
                for (int y : sb)
                    if (datas[x].idx == datas[y].idx) sc.insert(x), sc.insert(y);
            int pre;
            if (sc.empty()) cout << "Sorry, I found nothing.\n";
            else pre = datas[*sc.begin()].idx;
            for (auto x : sc) {
                if (datas[x].idx != pre) cout << "----------\n";
                pre = datas[x].idx;
                cout << datas[x].str << "\n";
            }
            cout << "==========\n";
        } else if (t == "OR") {
            ss >> t;
            tolow(tmp), tolow(t);
            set<int, cmp> sa, sb;
            sa = wordIdx[tmp], sb = wordIdx[t];
            for (int x : sb) sa.insert(x);
            int pre;
            if (sa.empty()) cout << "Sorry, I found nothing.\n";
            else pre = datas[*sa.begin()].idx;
            for (auto x : sa) {
                if (datas[x].idx != pre) cout << "----------\n";
                pre = datas[x].idx;
                cout << datas[x].str << "\n";
            }
            cout << "==========\n";
        } else if (tmp == "NOT") {
            tolow(t);
            set<int, cmp> sa = wordIdx[t];
            set<int> sb;
            for (int x : sa) {
                sb.insert(datas[x].idx);
            }
            int pre;
            if (sb.size() == n) cout << "Sorry, I found nothing.\n";
            else {
                bool flag = false;
                for (int i = 0; i < datas.size(); i++) {
                    if (sb.count(datas[i].idx)) continue;
                    if (flag && datas[i].idx != pre) cout << "----------\n";
                    else flag = true;
                    pre = datas[i].idx;
                    cout << datas[i].str << "\n";
                }
            }
            cout << "==========\n";
        } else {
            tolow(tmp);
            set<int, cmp> sa = wordIdx[tmp];
            int pre;
            if (sa.empty()) cout << "Sorry, I found nothing.\n";
            else pre = datas[*sa.begin()].idx;
            for (auto x : sa) {
                if (datas[x].idx != pre) cout << "----------\n";
                pre = datas[x].idx;
                cout << datas[x].str << "\n";
            }
            cout << "==========\n";
            flag = false;
        }
    }
    return 0;
}