M06640: 倒排索引

data structures, http://cs101.openjudge.cn/pctbook/M06640/

思路：用 map<string, set<int>> 建立倒排索引：key 为单词，value 为出现该单词的文档编号集合。

#include <iostream>
#include <map>
#include <set>
#include <string>
using namespace std;

int main() {
    int N;
    cin >> N;

    map<string, set<int>> invertedIndex;

    for (int i = 1; i <= N; i++) {
        int c;
        cin >> c;
        for (int j = 0; j < c; j++) {
            string word;
            cin >> word;
            invertedIndex[word].insert(i);
        }
    }

    int M;
    cin >> M;
    while (M--) {
        string query;
        cin >> query;
        if (invertedIndex.count(query) == 0)
            cout << "NOT FOUND\n";
        else {
            bool first = true;
            for (int id : invertedIndex[query]) {
                if (!first) cout << " ";
                cout << id;
                first = false;
            }
            cout << "\n";
        }
    }
    return 0;
}