你好！作为金牌教练，我非常高兴看到你已经掌握了 Trie 树的基础维护。现在我们要进入 Trie 树的一个非常经典的应用场景：最短前缀匹配。

在 LeetCode 的“单词替换”题目中，核心逻辑是在字典中找到能够匹配单词的最短“词根”。这在 NOI 竞赛中属于“字符串处理”类题目，通常考察选手对 Trie 树搜索过程的灵活控制。

---

题目名称：Replace Words (单词替换)

题目描述

在英语中，我们有一个概念叫做 词根 (root)。词根后面可以附带其他字符形成一个更长的单词——我们称之为 继承词 (successor)。例如，词根 an 后面附带 swer 形成继承词 answer。

现在给定一个由许多词根组成的字典 dictionary 和一个由空格隔开的继承词组成的句子 sentence。

你需要将句子中的每个 继承词 替换成字典中的 词根。

• 如果继承词有多个词根可以匹配，请用 最短 的词根替换它。
• 如果继承词没有对应的词根，则保留原词。

请输出替换完成后的句子。

输入格式

第一行包含一个整数 $N$，表示字典中词根的数量。 第二行包含 $N$ 个字符串，表示字典中的词根，字符串之间用空格隔开。 第三行包含一个字符串，表示待处理的句子（包含空格）。

输出格式

输出一行字符串，表示替换后的结果。

样例数据

样例 1： 输入：

3
cat bat rat
the cattle was rattled by the battery

输出：

the cat was rat by the bat

样例 2： 输入：

3
a b c
aadsfasf absbs bbab cadsfafs

输出：

a a b c

数据规模说明

• $1 \le N \le 1000$
• 每个词根长度在 $1 \le L_{root} \le 100$ 之间。
• 句子长度在 $1 \le L_{sentence} \le 10^6$ 之间。
• 所有字符均为小写英文字母。
• 注意：在 NOI 竞赛中，处理包含空格的整行句子建议使用 getline。

---

预备知识点

1. Trie 树构建：将所有词根插入 Trie 树。
2. 最短前缀搜索：在 Trie 树上查找继承词时，一旦遇到第一个 is_end 标记，立即返回。这就是该单词匹配到的最短词根。
3. 字符串分割：将句子按空格切分成单词处理。

---

启发式思路引导（草稿纸推演）

1. 最短原则的实现：
   • 假设字典里有 app 和 apple。
   • 对于单词 applepie：
     • 按照 Trie 树从根向下走：a -> p -> p。
     • 此时发现 p 节点有一个 is_end 标记。
     • 停止搜索！因为我们要找的是最短词根，app 已经满足要求，后面的 l, e 无需再看。
2. 搜索失败的处理：
   • 如果走着走着路径断了（遇到空指针），或者走完了单词都没遇到 is_end。
   • 结论：字典里没有它的词根，保留原词输出。
3. 句子重组：
   • 替换是逐个单词进行的，输出时记得在单词之间补回空格。

---

核心逻辑流程图（伪代码提示）

1. 插入词根 (Insert Roots)

与标准 Trie 插入一致，在末尾打上 is_end 标记。

2. 寻找最短词根 (Find Shortest Root)

这是本题的核心变算。

graph TD
    Start("开始: findShortest word") --> Init("p = 0, res_str = 空")
    Init --> Loop{"遍历 word 中的字符 c"}
    Loop -- "还有字符" --> GetID("id = c 减去 'a'")
    GetID --> CheckExist{"trie(p, id) 为 0 ?"}
    CheckExist -- "是 (断路)" --> RetOrig("返回原始 word")
    CheckExist -- "否" --> Move("p = trie(p, id)")
    Move --> AddChar("res_str 添加字符 c")
    AddChar --> CheckEnd{"is_end(p) 为真 ?"}
    CheckEnd -- "是 (找到最短词根)" --> RetRoot("返回 res_str")
    CheckEnd -- "否" --> Loop
    Loop -- "遍历完仍未发现标记" --> RetOrig

---

复杂度分析思考过程

1. 时间复杂度：
   • 建树：$O(\sum L_{root})$，所有词根长度之和。
   • 替换：句子总长度为 $M$，每个字符在 Trie 树上最多被访问一次，复杂度为 $O(M)$。
   • 总复杂度：$O(\sum L_{root} + M)$。这在 $10^6$ 规模下是非常理想的。
2. 空间复杂度：
   • $O(\sum L_{root} \times 26)$。
   • 相比于暴力 substr 比对，Trie 树极大地节省了重复前缀的空间。
3. 优化建议：
   • 在 NOI 竞赛中，频繁的字符串拼接（res_str += c）可能会慢。可以记录最短词根的长度，最后用原始字符串的 substr 或直接输出。

---

读题关键词总结

• “词根 (root)”：提示使用前缀相关的数据结构（Trie 树）。
• “最短”：提示在 Trie 树搜索时，遇到第一个结尾标记就停止。这是此题与普通搜索的关键区别。
• “空格隔开的句子”：提示需要进行字符串拆分逻辑。

---

NOI 风格解法建议（部分伪代码思路）

// 静态 Trie 数组
int trie[MAX_NODES][26];
bool is_end[MAX_NODES];
int tot = 0;

// 插入函数 (标准)
void insert(string s) { ... }

// 核心：查询函数
string findRoot(string s) {
    int p = 0;
    string cur = "";
    for (char c : s) {
        int id = c - 'a';
        if (!trie[p][id]) break; // 路径断了
        p = trie[p][id];
        cur += c;
        if (is_end[p]) return cur; // 关键：一遇到标记就返回最短的
    }
    return s; // 没找到，返回原词
}

// 主函数逻辑
// 1. 读入词根数量并 insert
// 2. 读入整行句子: getline(cin, sentence)
// 3. 用 stringstream 拆分单词或手动扫描
// 4. 对每个词调用 findRoot 并输出

希望这个引导能帮你顺利通关“单词替换”！记住，最短前缀匹配是 Trie 树最能体现其高效性的地方，因为它在搜索过程中具有天然的“早停”优势。准备好在草稿纸上模拟那个“遇标记即停”的过程了吗？