题解 | #阅读理解#

1. 问题分析

该问题是一个典型的全文检索（Full-Text Search）系统的简化模型。核心需求是构建从“关键词”到“文档ID”的映射关系，在工程中被称为倒排索引（Inverted Index）构建。

关键约束

1. 数据规模：
   • 文档数 ，每篇文档单词数 。总单词量级约为 。
   • 查询次数 。
   • 这是一个典型的读多写少场景（一次构建，多次查询）。
2. 性能瓶颈：
   • 如果采用在线性扫描（Brute Force）的方式处理每次查询，时间复杂度将达到 （为单词长度），约为 次操作，存在超时风险。
   • 必须将计算负载前置到“预处理”阶段，将查询的时间复杂度降低到接近 或 。
3. 数据一致性与细节：
   • 文档内去重：同一个单词在一篇文档中可能出现多次，但输出的文档ID列表中，该文档编号只能出现一次。
   • 有序性：要求输出的文档编号按升序排列。由于输入就是按 到 顺序给出的，利用这一自然序可以避免额外的排序操作。

2. 核心算法：倒排索引 (Inverted Index) + 哈希表 (Hash Map)

为了满足 级别的查询响应，我们需要构建一个映射结构：Map<String, List<Integer>>。

1. 数据结构选择：

   • Key (单词)：使用哈希表（Hash Map）存储单词。哈希表在平均情况下提供 的查找和插入效率（ 为字符串长度）。虽然字典树（Trie）在处理字符串前缀时更优，但在此题规模下，哈希表的实现复杂度更低且性能足以满足需求。
   • Value (文档ID列表)：使用动态数组（Dynamic Array / Vector）。由于我们按顺序（）处理文档，只要按序插入，该数组天然保持有序，无需后续排序算法。

2. 去重策略：

   • 在处理第 篇文档的某个单词 时，检查 对应的 ID 列表。如果列表为空，或者列表的最后一个元素不等于 ，则将 追加到列表末尾。这利用了处理的时序性巧妙地解决了单文档内重复单词的问题。

3. 代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    unordered_map<string, vector<int>> dict;

    for (int i = 1; i <= N; i++) {
        int L;
        cin >> L;
        for (int j = 0; j < L; j++) {
            string w;
            cin >> w;
            if (dict[w].empty() || dict[w].back() != i) {
                dict[w].push_back(i);
            }
        }
    }

    int M;
    cin >> M;

    while (M--) {
        string w;
        cin >> w;
        for (int idx : dict[w]) {
            cout << idx << " ";
        }
        cout << "\n";
    }
}