原创水题：Fish 笑传之查查补

本系列为原创垃圾水题，供学校新生天梯赛等算法竞赛以及博君一笑之用。

与其说是算法题，不如说是以模拟为主的思维题。

题目描述

在计算机科学中，Shell 是指一种提供用户与操作系统交互的界面程序。之所以称其为“壳”，是因为它起到“封装”操作系统底层（即 Kernel）的作用，屏蔽用户直接与内核的交互，同时管理用户的命令输入和操作系统的响应。

Shell和Kernel的关系

Shell 通常分为命令行 Shell 和图形 Shell。如 Windows 中的“文件资源管理器”就是一个典型的图形 Shell，允许用户通过图形界面与系统交互。但狭义的 Shell 单指前者，本题中的 Shell 指的是命令行 Shell。

在 Windows 系统中，常见的 Shell 包括 cmd.exe（命令提示符）和 PowerShell。而在 UNIX 系统及其衍生系统中，Shell 的种类更加丰富。以下是几种经典的 UNIX Shell：

sh（Bourne Shell）：最初的 UNIX Shell，也是最为经典的版本。
ash（Almquist Shell）：优化了性能，广泛用于 BSD 系统。
bash（Bourne-Again Shell）：借鉴了多个 Shell 的功能，成为大多数 Linux 系统的默认 Shell。
zsh（Z Shell）：对 sh 做了许多改进，并引入其他 Shell 的特性，自 2019 年起成为 macOS 的默认 Shell。
fish（Friendly Interactive Shell）：旨在提供更友好的交互体验，拥有智能的命令补全功能，适用于大部分平台。

其中，fish 以其智能、高效的命令补全功能闻名。它不仅能根据可执行文件的名称进行自动补全，还可以基于用户定义的脚本、上下文环境以及历史命令进行动态补全，极大提升了用户的工作效率。下面展示了基于可执行文件和历史命令的补全示例：

基于可执行文件进行补全的例子
基于已有历史命令进行补全的例子

Charles 非常喜欢使用 fish，并决定实现一个简化版的动态补全引擎，帮助他在日常工作中快速完成指令补全。这个引擎基于一组预定义的补全规则，能够根据用户输入的前缀迅速返回所有匹配的补全结果。为了满足不同场景的需求，补全规则分为两种类型：

全局规则：适用于所有上下文的补全。
上下文规则：仅在特定上下文下生效的补全规则。

每条补全规则由以下部分组成：

规则类型：全局规则 global 或上下文规则 context。
触发条件（仅适用于上下文规则）：规则的适用范围，例如特定命令（如 git）或路径（如 /home/charles/）。
补全词列表：该规则提供的补全词。

Charles 的引擎需要支持以下功能：

根据用户输入的前缀，结合所有匹配的规则，输出补全结果。
当全局规则和上下文规则冲突时（即同一前缀的补全结果不同），优先选择上下文规则。

你需要帮助 Charles 实现他的补全引擎，并完成一系列动态补全任务。

输入描述

第一行包含两个整数 $R$ 和 $Q$ $(1 \le R, Q \le 100)$，分别表示补全规则数量和查询数量。

接下来包含 $R$ 条补全规则，每条补全规则的格式如下：

第一行为规则类型，可能是全局规则 global 或上下文规则 context。
如果规则是 context 类型，接下来一行包含触发条件（一个字符串，表示上下文）。
接着是补全词列表：第一行是整数 $n$ $(1 \le n \le 50)$，表示补全词的个数，紧接着是 $n$ 个以空格分隔的补全词。

接下来 $Q$ 行，每行包含一个查询，格式为 上下文前缀。

其中，若上下文为 . 则表示无上下文（仅适用全局规则），前缀为用户输入的非空字符串。

保证输入的字符串长度均不超过 $127$，不同规则的触发条件可能相同，补全词列表中的词也可能重复。

输出描述

对于每个查询，输出一行，包含去重后的补全结果，按照字典序排列并以空格分隔。

如果没有匹配的补全结果，或输入的命令已经是完整的且无法进行下一步补全，输出 EMPTY。

样例

输入数据 1

4 6
global
3 ls cd echo
context
git
4 add addon commit push
context
/home/charles/
2 work personal
global
2 help exit
. l
git add
git addon
/home/charles/ p
/home/charles/ w
/home/frex/ x

输出数据 1

ls
add addon
EMPTY
personal
work
EMPTY

输入数据 2

2 5
global
6 a ab abc b bc bcd
context
echo
3 a ac ak
echo a
echo ac
echo b
. b
ls a

输出数据 2

a ac ak
EMPTY
EMPTY
b bc bcd
a ab abc

提示

样例解释

对于样例 $1$：
- 规则解析：
  1. 第一条规则为全局规则，提供的补全词是：ls，cd，echo。
  2. 第二条规则为上下文规则，适用于 git 命令，补全词是：add，addon，commit，push。
  3. 第三条规则为上下文规则，适用于路径 /home/charles/，补全词是：work，personal。
  4. 第四条规则为全局规则，提供的补全词是：help，exit。
- 查询解析：
  1. 查询 . l：
    - 没有上下文，只有全局规则适用。全局规则提供了补全词 cd，echo，exit，help，ls。
    - l 前缀匹配补全词 ls，所以输出：ls。
  2. 查询 git add：
    - 上下文为 git，适用第二条规则，提供补全词：add，addon，commit，push。
    - add 前缀匹配补全词 add 和 addon，所以输出：add addon。
  3. 查询 git addon：
    - 上下文为 git，适用第二条规则，提供补全词：add，addon，commit，push。
    - addon 已经是完整的命令，无法继续补全，输出：EMPTY。
  4. 查询 /home/charles/ p：
    - 上下文为 /home/charles/，适用第三条规则，提供补全词：personal，work。
    - p 前缀匹配补全词 personal，所以输出：personal。
  5. 查询 /home/charles/ w：
    - 上下文为 /home/charles/，适用第三条规则，提供补全词：personal，work。
    - w 前缀匹配补全词 work，所以输出：work。
  6. 查询 /home/frex/ x：
    - 上下文为 /home/frex/，没有对应的上下文规则，只有全局规则适用。全局规则提供了补全词 cd，echo，exit，help，ls。
    - 没有与 x 匹配的补全词，无法进行补全，输出：EMPTY。
对于样例 $2$：
- 规则解析：
  1. 第一条规则为全局规则，提供的补全词是：a，ab，abc，b，bc，bcd。
  2. 第二条规则为上下文规则，适用于 echo 命令，补全词是：a，ac，ak。
- 查询解析：
  1. 查询 echo a：
    - 上下文为 echo，适用第二条规则，提供补全词：a，ac，ak。
    - a 前缀匹配补全词 a，ac，ak，所以输出：a ac ak。
  2. 查询 echo ac：
    - 上下文为 echo，适用第二条规则，提供补全词：a，ac，ak。
    - ac 已经是完整的命令，无法继续补全，输出：EMPTY。
  3. 查询 echo b：
    - 上下文为 echo，适用第二条规则，提供补全词：a，ac，ak。
    - 没有与 b 匹配的补全词，无法进行补全，输出：EMPTY。
  4. 查询 . b：
    - 没有上下文，只有全局规则适用。全局规则提供了补全词 a，ab，abc，b，bc，bcd。
    - b 前缀匹配补全词 b，bc，bcd，所以输出：b bc bcd。
  5. 查询 ls a：
    - 上下文为 ls，没有对应的上下文规则，只有全局规则适用。全局规则提供了补全词 a，ab，abc，b，bc，bcd。
    - a 前缀匹配补全词 a，ab，abc，所以输出：a ab abc。

思路

~~思路？你怕不是在说笑吧？~~
~~这么大份的题我怎么可能会有思路？~~

这道题其实是一个经典的字典树 Trie 的简化版本。

核心的数据结构包括：

context: map<string, set<string>> - 存储每个上下文对应的单词集合；
global: set<string> - 存储全局单词集合（默认上下文）。

补全词去重的工作交给set<string>完成就好。

题解

#include <bits/stdc++.h>

int main() {
    int R, Q;
    std::cin >> R >> Q;

    std::map<std::string, std::set<std::string>> context;
    std::set<std::string> global;
    while (R--) {
        std::string rule;
        std::cin >> rule;

        if (rule == "context") {
            std::string condition;
            std::cin >> condition;

            int n;
            std::cin >> n;
            for (int i = 0; i < n; i++) {
                std::string word;
                std::cin >> word;
                context[condition].emplace(word);
            }
        } else {
            int n;
            std::cin >> n;
            for (int i = 0; i < n; i++) {
                std::string word;
                std::cin >> word;
                global.emplace(word);
            }
        }
    }

    while (Q--) {
        std::string con, pre;
        std::cin >> con >> pre;
        std::vector<std::string> ans;

        if (context.count(con)) {
            for (auto s : context[con]) {
                if (s.size() >= pre.size() && s.substr(0, pre.size()) == pre) {
                    ans.emplace_back(s);
                }
            }
        } else {
            for (auto s : global) {
                if (s.size() >= pre.size() && s.substr(0, pre.size()) == pre) {
                    ans.emplace_back(s);
                }
            }
        }

        if (ans.empty() || ans.size() == 1 && ans[0] == pre) {
            std::cout << "EMPTY\n";
        } else {
            for (int i = 0; i < ans.size(); i++) {
                std::cout << ans[i] << " \n"[i + 1 == ans.size()];
            }
        }
    }
}

算法

#算法 #题解 #模拟

原创水题：Fish 笑传之查查补

https://blog.charles-link.cn/2025/10/原创水题：Fish 笑传之查查补/

作者

Charles

发布于

2025年10月16日

许可协议

原创水题：重力井上一篇

本土化 OnlyOffice Document Server 配置流程下一篇