题目描述

题目模拟了一种叫做“蛇语”的加密方式。规则如下：

1. 加密（虽然题目是解密，但理解加密有助于理解）： 对一句话 A，提取每个字（拼音词）的首字母，形成一个首字母缩写字符串。然后找到（或编造）另一句话 B，要求 B 中每个字的首字母与 A 提取出的首字母序列完全相同。
2. 解密（本题任务）： 给定一个“蛇语”句子（即上面规则中的 B），我们需要在一个已知的“蛇语词典”（包含很多可能的原始句子）中，找出所有首字母缩写与该蛇语句子相同的原始句子。

具体任务：
读入一个包含 N 个句子的词典。
读入 M 个需要查询（翻译）的蛇语句子。
* 对每个查询句子：
* 计算它的首字母缩写。
* 在词典中查找所有首字母缩写与之相同的句子。
* 如果找到一个或多个匹配的句子：按字母顺序将它们排序，并用 | 分隔输出。
* 如果没有找到匹配的句子：将查询的句子原样输出。

输入格式：
第一行：词典大小 N。
接下来 N 行：每行一个词典句子（小写字母拼音，空格分隔）。
再下一行：查询次数 M。
接下来 M 行：每行一个待查询的句子（格式同词典）。

输出格式：
* 对每个查询，输出一行结果（匹配的句子列表或原查询句）。

数据范围：
$1 \le N \le 10^5$ (词典大小)
$1 \le M \le 10^3$ (查询次数)
句子长度 $\le 50$
每个拼音词长度 $\le 6$

样例

输入样例：

8                  // N = 8 个词典句子
yong yuan de shen
yong yuan de she
jing dong xin bai huo
she yu wo ye hui shuo yi dian dian
liang wei bu yao chong dong
yi  dian dian      // 注意这里 yi 和 dian dian 间有两个空格
ni hui shuo she yu a
yong yuan de sha
7                  // M = 7 次查询
jiu dian xia ban ha
shao ye wu ya he shui you dian duo
liu wan bu yao ci dao
ni hai shi su yan a
yao diao deng
sha ye ting bu jian
y y d s

输出样例：

jing dong xin bai huo                   // "jiu dian xia ban ha" -> jdxbh -> "jing dong xin bai huo"
she yu wo ye hui shuo yi dian dian      // "shao ye wu ya he shui you dian duo" -> sywyhsydd -> "she yu wo ye hui shuo yi dian dian"
liang wei bu yao chong dong              // "liu wan bu yao ci dao" -> lwbnycd -> "liang wei bu yao chong dong"
ni hui shuo she yu a                  // "ni hai shi su yan a" -> nhssya -> "ni hui shuo she yu a"
yi  dian dian                         // "yao diao deng" -> ydd -> "yi  dian dian" (注意保留了双空格)
sha ye ting bu jian                   // "sha ye ting bu jian" -> sytbj -> 未找到匹配 (词典中没有sytbj)，原样输出
yong yuan de sha|yong yuan de she|yong yuan de shen // "y y d s" -> yyds -> 找到3个匹配，排序后用 | 分隔输出

算法1

(哈希/映射 + 模拟)

思路:

核心问题是如何快速根据一个句子的首字母缩写找到词典中所有具有相同缩写的句子。这自然地指向使用哈希表或映射 (map) 数据结构。

1. 预处理词典：

   • 我们需要一个函数 get(string s) 来提取任意给定句子 s 的首字母缩写。
   • 遍历词典中的 N 个句子。
   • 对每个句子 s，计算其首字母缩写 t = get(s)。
   • 使用一个 map (或 unordered_map)，其中：
     • 键 (Key): 是首字母缩写字符串 t。
     • 值 (Value): 是一个存储了所有具有该缩写的原始词典句子的列表（例如 vector<string>）。
   • 将当前句子 s 添加到键为 t 的 vector 中。map<string, vector<string>> f; f[t].push_back(s);

2. 处理查询：

   • 对于 M 个查询中的每一个查询句子 q：
   • 计算查询句子 q 的首字母缩写 initial = get(q)。
   • 在之前构建的 map f 中查找键 initial 是否存在 (f.find(initial))。
   • 如果找不到 (f.find(initial) == f.end())： 说明词典中没有句子的首字母缩写与查询句相同。按照要求，直接输出原始查询句 q。
   • 如果找到了：
     • 获取与键 initial 关联的 vector<string> (即 it->second，其中 it 是 find 返回的迭代器)。
     • 根据题目要求，对这个 vector 中的句子进行字母序排序 (sort(t.begin(), t.end());)。
     • 遍历排序后的 vector，输出每个句子。在句子之间（除了最后一个句子之后）输出分隔符 |。

get(string &s) 函数实现细节:

代码中的 get 函数通过遍历字符串 s 来提取首字母：
使用一个布尔标志 ok，初始化为 true。ok 为 true 表示下一个遇到的非空格字符应该是某个词的首字母。
遍历字符串 s 中的每个字符 c：
* 如果 ok 是 true 并且 c 不是空格：说明 c 是一个词的首字母。将其追加到结果字符串 initial 中，并将 ok 设为 false（因为同一个词的后续字母不是首字母）。
* 如果 c 是空格：说明一个词结束了（或者可能是连续空格），将 ok 设回 true，以便能够识别下一个词的首字母。
返回最终构建的 initial 字符串。
注意: 这个实现能正确处理连续空格的情况，例如 “yi dian dian”，它会找到 ‘y’，遇到第一个空格设 ok=true，遇到第二个空格保持 ok=true，遇到 ‘d’ 时 ok 仍是 true，于是 ‘d’ 被加入，ok 变 false，之后遇到 ‘i’ 等直到空格，再将 ok 设为 true，找到下一个 ‘d’。最终得到 “ydd”。

代码逻辑详解:

1. 包含头文件和命名空间： #include <bits/stdc++.h> 和 using namespace std;。定义 i64 别名（本题未使用）。
2. 加速输入输出： ios::sync_with_stdio(false); cin.tie(nullptr);。
3. 读取词典大小 N： cin >> n;。
4. 处理换行符： cin.ignore(); 消耗掉读取 n 后 cin 缓冲区中残留的换行符，防止影响后续的 getline。
5. 定义 get 函数： 使用 lambda 表达式定义了上述提取首字母的逻辑。
6. 构建词典映射：
   • map<string, vector<string>> f; 创建映射。
   • 循环 n 次：
     • getline(cin, s); 读取一个词典句子。
     • string t = get(s); 计算首字母缩写。
     • f[t].push_back(s); 将原句 s 添加到缩写 t 对应的 vector 中。
7. 读取查询次数 M： cin >> m;。
8. 处理换行符： cin.ignore();。
9. 处理查询：
   • 循环 m 次：
     • getline(cin, q); 读取一个查询句子。
     • string initial = get(q); 计算查询句的首字母缩写。
     • auto it = f.find(initial); 在 map 中查找该缩写。
     • 判断是否找到：
       • if (it == f.end()): 没找到，输出原查询句 cout << q << "\n";。
       • else: 找到了。
         • vector<string> &t = it->second; 获取匹配句子列表的引用（避免拷贝）。
         • sort(t.begin(), t.end()); 对列表按字母序排序。
         • 格式化输出： 循环遍历排序后的列表 t。
           • cout << t[j]; 输出句子。
           • if (j < t.size() - 1) { cout << "|"; } 如果不是最后一个句子，输出分隔符 |。
         • cout << "\n"; 输出换行符结束本次查询的输出。
10. 程序结束： return 0;。

时间复杂度

1. get 函数: 遍历句子一次，复杂度 O(L)，其中 L 是句子长度 (L <= 50)。
2. 构建词典映射:
   • 对 N 个句子，每个句子调用 get 函数，总时间 O(N * L_avg)，L_avg 是平均句子长度。
   • 将 N 个句子插入 map。每次插入的键是缩写（长度也 <= L），值是句子本身。map 的插入操作平均是 O(log K * KeyLength)，K 是 map 中当前的键数量。总插入时间大致可以估计为 O(N * log N * L_avg)。
   • 总构建时间约为 O(N * L_avg + N * log N * L_avg) ≈ O(N * L * log N) （用 L_max=50 作为上界）。
3. 处理查询:
   • 对 M 个查询，每个查询：
     • 调用 get 函数：O(L)。
     • map.find 操作：O(log N * L) （比较键需要 L 时间）。
     • 如果找到，对结果 vector (大小设为 k) 排序：O(k log k * L) （字符串比较需要 L 时间）。k 最多是 N，但通常远小于 N。
     • 输出：O(k * L)。
   • 查询总时间约为 O(M * (L + log N * L + k_max * log k_max * L))。其中 k_max 是单个缩写对应的最大句子数。
   • 考虑到 M=1000, N=10^5, L=50, log N ≈ 17。复杂度约为 O(M * (L log N + k_max log k_max * L))。

整体时间复杂度 主要由构建字典和查询排序决定。大致为 O(N * L * log N + M * k_max * L * log k_max)。在给定数据范围下是可行的。

空间复杂度

• 主要开销是存储词典的 map。
• map 的键是缩写，值是原始句子的 vector。
• 最坏情况下，如果所有句子缩写都不同，空间复杂度约为 O(N * L)。如果很多句子缩写相同，则是一个缩写对应一个较长的 vector。
• 总空间复杂度是存储所有原始词典句子的总长度，即 O(N * L_avg) 或 O(TotalLength_Dictionary)。

C++ 代码

#include <bits/stdc++.h> // 引入所有标准库头文件

using namespace std; // 使用 std 命名空间
using i64 = long long; // 定义 i64 为 long long 的别名（本题未使用）

int main() {
    // 优化 C++ 输入输出流速度
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; // 词典句子数量
    cin >> n; // 读取 N
    cin.ignore(); // 忽略 cin 读取 n 后留下的换行符

    // 定义一个 lambda 函数 get，用于提取字符串 s 的首字母缩写
    // [&] 表示按引用捕获外部变量（虽然这里没用到）
    auto get = [&](string &s) {
        string initial; // 用于存储首字母缩写
        bool ok = true; // 标志位：true 表示下一个非空格字符是首字母
        // 遍历输入字符串 s 的每个字符 c
        for (char c : s) {
            // 如果 ok 为 true 且 c 不是空格，说明 c 是一个词的首字母
            if (ok and c != ' ') {
                initial += c; // 将 c 添加到缩写中
                ok = false; // 将 ok 设为 false，同一个词的后续字母不再是首字母
            }
            // 如果 c 是空格，表示一个词结束了（或连续空格），重置 ok 为 true
            if (c == ' ') {
                ok = true;
            }
        }
        return initial; // 返回提取到的首字母缩写
    };

    // 创建一个 map，键是首字母缩写(string)，值是包含所有该缩写的原始句子(vector<string>)
    map<string, vector<string>> f;
    // 循环读取 N 个词典句子
    for (int i = 0; i < n; i ++ ) {
        string s; // 存储当前读取的句子
        getline(cin, s); // 读取一整行句子
        string t = get(s); // 计算该句子的首字母缩写
        f[t].push_back(s); // 将原句 s 添加到缩写 t 对应的 vector 中
                         // map 的 [] 操作会自动创建键 t (如果不存在)
    }

    int m; // 查询次数
    cin >> m; // 读取 M
    cin.ignore(); // 忽略 cin 读取 m 后留下的换行符

    // 循环处理 M 次查询
    for (int i = 0; i < m; i ++ ) {
        string q; // 存储当前查询的句子
        getline(cin, q); // 读取一整行查询句
        string initial = get(q); // 计算查询句的首字母缩写

        // 在 map f 中查找是否存在键为 initial 的条目
        auto it = f.find(initial);
        // 如果迭代器 it 等于 f.end()，表示没有找到匹配的缩写
        if (it == f.end()) {
            cout << q << "\n"; // 按要求输出原始查询句
        } else {
            // 如果找到了匹配的缩写
            vector<string> &t = it->second; // 获取该缩写对应的句子列表的引用 (提高效率)
            sort(t.begin(), t.end()); // 对句子列表按字母顺序排序
            // 遍历排序后的句子列表
            for (int j = 0; j < t.size(); j ++ ) {
                cout << t[j]; // 输出当前句子
                // 如果不是最后一个句子，输出分隔符 "|"
                if (j < t.size() - 1) {
                    cout << "|";
                }
            }
            cout << "\n"; // 输出换行符，结束本次查询的输出
        }
    }

    return 0; // 程序正常结束
}