针对“单词替换”这一经典 Trie 树应用题，我们需要生成能够覆盖最短前缀匹配逻辑的数据。特别需要关注词根是另一个词根的前缀、词根比继承词长、句子中包含大量无法匹配的单词等情况。

以下是完整的数据生成器代码，它集成了标准 Trie 树逻辑来生成 .out 文件。

数据生成器代码 (C++14)

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <random>
#include <algorithm>
#include <cstring>
#include <sstream>

using namespace std;

// --- 竞赛标准 Trie 实现 (用于同步生成 .out) ---
const int MAX_NODES = 200005; // 足够容纳 1000 * 100 规模的词根
int trie[MAX_NODES][26];
bool is_end[MAX_NODES];
int tot = 0;

void reset_trie() {
    for (int i = 0; i <= tot; ++i) {
        memset(trie[i], 0, sizeof(trie[i]));
        is_end[i] = false;
    }
    tot = 0;
}

void insert(const string& s) {
    int p = 0;
    for (char c : s) {
        int id = c - 'a';
        if (!trie[p][id]) trie[p][id] = ++tot;
        p = trie[p][id];
    }
    is_end[p] = true;
}

string query(const string& word) {
    int p = 0;
    string res = "";
    for (char c : word) {
        int id = c - 'a';
        if (!trie[p][id]) return word;
        p = trie[p][id];
        res += c;
        if (is_end[p]) return res; // 最短匹配逻辑
    }
    return word;
}

// --- 随机引擎 ---
mt19937 rng(20260111);

string gen_string(int len, int alpha) {
    string s = "";
    for (int i = 0; i < len; ++i) s += (char)('a' + (rng() % alpha));
    return s;
}

/**
 * t_idx: 测试点序号
 * n: 词根数量
 * max_root_l: 词根最大长度
 * m: 句子中单词数量
 * max_word_l: 单词最大长度
 * alpha: 字符集大小
 * match_bias: 匹配倾向 (0-100)，越高越容易产生匹配
 */
void make_data(int t_idx, int n, int max_root_l, int m, int max_word_l, int alpha, int match_bias) {
    string in_name = to_string(t_idx) + ".in";
    string out_name = to_string(t_idx) + ".out";
    ofstream fin(in_name);
    ofstream fout(out_name);

    reset_trie();
    vector<string> roots;
    
    // 1. 生成词根
    for (int i = 0; i < n; ++i) {
        string r = gen_string(1 + rng() % max_root_l, alpha);
        roots.push_back(r);
        insert(r);
    }
    
    // 写入字典部分
    fin << n << "\n";
    for (int i = 0; i < n; ++i) fin << roots[i] << (i == n - 1 ? "" : " ");
    fin << "\n";

    // 2. 生成句子并同步计算答案
    string sentence = "";
    string output = "";
    for (int i = 0; i < m; ++i) {
        string word;
        if (rng() % 100 < match_bias && !roots.empty()) {
            // 构造一个倾向于匹配的单词
            string root = roots[rng() % roots.size()];
            word = root + gen_string(rng() % max_word_l, alpha);
        } else {
            // 完全随机单词
            word = gen_string(1 + rng() % max_word_l, alpha);
        }
        
        sentence += word;
        output += query(word);
        
        if (i != m - 1) {
            sentence += " ";
            output += " ";
        }
        
        // 剪枝：如果句子太长（超过 1.5MB），提前截断防止输入文件过大
        if (sentence.length() > 1200000) break;
    }
    
    fin << sentence << "\n";
    fout << output << "\n";

    fin.close();
    fout.close();
    cout << "Testcase " << t_idx << " [N=" << n << " M_chars=" << sentence.length() << "] done." << endl;
}

int main() {
    // 1-2: 极小数据/基础逻辑（包含只有1个字母的词根）
    make_data(1, 5, 3, 10, 5, 26, 50);
    make_data(2, 10, 5, 50, 10, 3, 70);

    // 3-4: 深度与前缀覆盖测试
    make_data(3, 100, 50, 1000, 10, 1, 100); // 全 'a' 环境，测试最短路径
    make_data(4, 200, 20, 2000, 50, 2, 80);  // 仅 'a','b'

    // 5-6: 零匹配与长单词测试
    make_data(5, 500, 10, 5000, 100, 26, 0); // 倾向 0，测试原词保留
    make_data(6, 100, 100, 1000, 200, 26, 50);

    // 7-8: 大规模句子，中等词根
    make_data(7, 800, 50, 50000, 20, 26, 60);
    make_data(8, 1000, 20, 100000, 15, 26, 40);

    // 9-10: 极限规模（句子长度接近 10^6）
    make_data(9, 1000, 100, 150000, 10, 26, 50);
    make_data(10, 1000, 10, 200000, 5, 5, 90); // 小字符集，极高匹配率

    return 0;
}

生成器设计细节与优化建议：

1. 文件大小控制：

   • 本题最大的挑战是 sentence 长度。如果按 $M=200,000$ 且单词长度平均 5 计算，句子长度约为 $10^6$。
   • 生成器中加入了 sentence.length() > 1200000 的剪枝判断，确保单个 .in 文件大小在 1.2MB 左右，全套数据在压缩后非常小，符合“理想值 2MB”的要求。

2. 正常与边界情况覆盖：

   • Case 3 (alpha=1)：构造了极深的单链树，测试 Trie 树的深度。
   • Case 5 (match_bias=0)：测试词根字典与句子完全不匹配时，程序能否正确返回原词。
   • Case 10 (alpha=5, bias=90)：测试极短词根命中大量单词的情况。
   • 随机倾向性：通过 match_bias 强制构造带有词根前缀的单词，避免了随机生成的单词由于组合数学概率太低而导致无法命中词根的情况。

3. 效率与安全：

   • 非递归：Trie 的 insert 和 query 均采用迭代（for 循环）实现，绝无爆栈风险。
   • 防止除以0：随机长度使用 1 + rng() % max_L，确保分母或长度永远不为 0。
   • 内存重置：reset_trie 仅清理已使用的 tot 范围，提高生成多组大数据的速度。

4. NOI/NOIP 读题关键词总结：

   • “替换”+“前缀”：这是 Trie 树的标准应用提示。
   • “最短”：在 Trie 遍历时，if (is_end[p]) return res; 这一行必须写在循环体内的最前面（一旦找到标记立即返回）。
   • “空格隔开”：提示在处理输入时不能直接 cin >> string（会跳过空格），需要用到 stringstream 或者手动处理 getchar()。在本题中，stringstream 是处理这类句子的 C++ 标准利器。

对于“单词替换”这道题，我们从最直观的暴力匹配开始，逐步过渡到 NOI 竞赛中最常用的 Trie 树最优解。

版本 1：暴力匹配版 (Brute Force)

思路：将字典存储在 vector 中。对于句子中的每个单词，遍历整个字典，检查是否有词根是该单词的前缀。如果有多个匹配，记录最短的一个。

#include <iostream>
#include <vector>
#include <string>
#include <sstream>

using namespace std;

// 检查 root 是否是 word 的前缀
bool isPrefix(const string& root, const string& word) {
    if (root.size() > word.size()) return false;
    return word.compare(0, root.size(), root) == 0;
}

int main() {
    int n;
    if (!(cin >> n)) return 0;
    vector<string> dict(n);
    for (int i = 0; i < n; ++i) cin >> dict[i];

    string line;
    getline(cin >> ws, line); // ws 过滤掉之前的换行符
    stringstream ss(line);
    string word, result = "";

    bool first = true;
    while (ss >> word) {
        string shortestRoot = word;
        for (const string& root : dict) {
            if (isPrefix(root, word)) {
                // 如果找到更短的词根，更新
                if (root.size() < shortestRoot.size()) {
                    shortestRoot = root;
                }
            }
        }
        if (!first) result += " ";
        result += shortestRoot;
        first = false;
    }
    cout << result << endl;
    return 0;
}

• 时间复杂度分析：
  • 假设字典有 $N$ 个词，句子有 $M$ 个单词，单词平均长度为 $L$。
  • 复杂度为 $O(M \times N \times L)$。当 $N$ 和 $M$ 都较大时，会严重超时。
• 空间复杂度：$O(N \times L)$，存储字典。

版本 2：哈希表优化版 (Hash Set)

思路：利用 unordered_set 存储词根。对于句子中的每个单词，从长度 1 开始截取前缀，去哈希表中查询。一旦查到，说明这是最短词根。

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <unordered_set>

using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(0); // 竞赛必备加速
    int n;
    cin >> n;
    unordered_set<string> dict;
    for (int i = 0; i < n; ++i) {
        string root; cin >> root;
        dict.insert(root);
    }

    string line;
    getline(cin >> ws, line);
    stringstream ss(line);
    string word;
    bool first = true;

    while (ss >> word) {
        string replace = word;
        // 尝试从长度 1 到 word.length() 截取前缀
        for (int i = 1; i <= word.length(); ++i) {
            string sub = word.substr(0, i);
            if (dict.count(sub)) {
                replace = sub;
                break; // 找到最短的，立即跳出
            }
        }
        if (!first) cout << " ";
        cout << replace;
        first = false;
    }
    cout << endl;
    return 0;
}

• 复杂度分析：
  • 时间：$O(\sum L_{root} + M \times L^2)$。substr 和哈希计算都需要 $O(L)$，循环 $L$ 次，所以是 $O(L^2)$。
  • 空间：$O(\sum L_{root})$。
• 优化建议：虽然比版本 1 快，但频繁构造 substr 依然有常数开销。

版本 3：Trie 树最优版 (NOIP 竞赛风格)

核心思想：利用 Trie 树的结构。在搜索单词时，只要碰到第一个 is_end 标记，就说明找到了最短词根。

#include <iostream>
#include <string>
#include <vector>
#include <sstream>

using namespace std;

// 竞赛常数定义：根据规模设定
// 总词根长度约 1000 * 100 = 10^5
const int MAXN = 100005;

int trie[MAXN][26];
bool is_end[MAXN];
int tot = 0;

// 标准插入函数
void insert(const string& s) {
    int p = 0;
    for (char c : s) {
        int id = c - 'a';
        if (!trie[p][id]) trie[p][id] = ++tot;
        p = trie[p][id];
    }
    is_end[p] = true;
}

// 核心逻辑：寻找最短匹配前缀
string findShortestRoot(const string& word) {
    int p = 0;
    string res = "";
    for (char c : word) {
        int id = c - 'a';
        // 如果路径断了，说明没有匹配的词根
        if (!trie[p][id]) return word;
        
        p = trie[p][id];
        res += c;
        // 关键点：一旦遇到标记，说明找到了最短词根
        if (is_end[p]) return res;
    }
    return word;
}

int main() {
    // 1. 加速 I/O
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    if (!(cin >> n)) return 0;
    for (int i = 0; i < n; ++i) {
        string root;
        cin >> root;
        insert(root);
    }

    // 2. 处理带空格的整行句子
    string line;
    getline(cin >> ws, line); 
    
    // 3. 单词拆分处理
    stringstream ss(line);
    string word;
    bool first = true;
    while (ss >> word) {
        if (!first) cout << " ";
        // 4. 调用 Trie 树查询
        cout << findShortestRoot(word);
        first = false;
    }
    cout << endl;

    return 0;
}

复杂度分析思考过程：

1. 时间复杂度分析：

   • 构建树：$O(\sum L_{root})$，每个字符只访问一次。
   • 单词查询：对于句子中的每个字符，在 Trie 树上最多向下走一步。总时间复杂度为 $O(\text{句子总长度})$。
   • 结论：这是最优复杂度 $O(S)$，其中 $S$ 是所有输入字符的总和。

2. 空间复杂度分析：

   • $O(\text{节点总数} \times 26)$。在本题规模下（$10^5$ 节点），占用内存约为 $10^5 \times 26 \times 4$ 字节 $\approx 10$ MB，远低于常规竞赛 128MB 的限制。

3. 易错点（教练提示）：

   • 换行符污染：在 cin >> n 之后紧跟 getline 会读到一个残留的空行。使用 getline(cin >> ws, line) 可以完美跳过前导空格和换行。
   • 最短原则：在 findShortestRoot 中，if (is_end[p]) 必须在循环内优先判断并立即 return。如果走到底才判断，就变成了“最长匹配”。
   • 数组范围：MAXN 必须开够，否则会 Segmentation Fault。在 NOI 竞赛中，通常根据“字符串总长度”来估算节点数。

时间复杂度优化建议：

• 如果句子长度达到 $10^6$ 且对效率要求极高，可以不使用 stringstream 和 string +=，而是直接对 line 字符串进行单指针扫描，遇到空格直接输出并重置 Trie 指针，这样可以实现“零拷贝”处理，速度最快。