针对“单词替换”这一经典 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++ 标准利器。