作为 NOI 教练，制作模拟题数据时，最重要的是覆盖逻辑边界。对于“Word Pattern”这类映射题，数据必须包含：长度不等、多对一映射、一对多映射、以及大规模极限数据。

以下是为您准备的 C++14 数据生成器。它将逻辑解题函数与数据生成逻辑结合，自动产出 1.in/out 到 10.in/out。

一、 数据生成策略

1. Test 1-2 (基础验证)：手动构造的小规模数据（True/False）。
2. Test 3 (长度不匹配)：pattern 长度与单词数量不等。
3. Test 4 (一对多失败)：同一个字符尝试映射到两个不同的单词。
4. Test 5 (多对一失败)：两个不同的字符尝试映射到同一个单词（这是学生最容易漏掉的逻辑）。
5. Test 6 (单字符极限)：pattern 和 s 都只有一个元素。
6. Test 7-8 (最大规模匹配)：$N=300$，$M=3000$，字符与单词一一对应，结果为 true。
7. Test 9-10 (混合随机)：随机生成单词和字符，测试综合鲁棒性。

二、 数据生成器源码 (C++14)

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <sstream>
#include <random>
#include <chrono>

using namespace std;

// --- 逻辑求解器：用于生成 .out 文件 ---
string solve(string pattern, string s) {
    vector<string> words;
    stringstream ss(s);
    string t;
    while (ss >> t) words.push_back(t);

    if (pattern.length() != words.size()) return "false";

    map<char, string> p2s;
    map<string, char> s2p;

    for (int i = 0; i < (int)pattern.length(); ++i) {
        char c = pattern[i];
        string w = words[i];
        if (p2s.count(c) && p2s[c] != w) return "false";
        if (s2p.count(w) && s2p[w] != c) return "false";
        p2s[c] = w;
        s2p[w] = c;
    }
    return "true";
}

// --- 数据生成逻辑 ---
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// 生成随机小写单词
string gen_word(int len) {
    string res = "";
    for (int i = 0; i < len; ++i) res += (char)('a' + rng() % 26);
    return res;
}

void make_data(int id) {
    string in_name = to_string(id) + ".in";
    string out_name = to_string(id) + ".out";
    ofstream fout(in_name);

    string pattern = "";
    string s = "";
    vector<string> words;

    if (id == 1) { // 简单匹配
        pattern = "abba";
        words = {"dog", "cat", "cat", "dog"};
    } else if (id == 2) { // 简单不匹配
        pattern = "abba";
        words = {"dog", "cat", "cat", "fish"};
    } else if (id == 3) { // 长度不等
        pattern = "abc";
        words = {"dog", "cat"};
    } else if (id == 4) { // 一对多失败
        pattern = "aaaa";
        words = {"dog", "dog", "cat", "dog"};
    } else if (id == 5) { // 多对一失败
        pattern = "abcd";
        words = {"dog", "dog", "dog", "dog"};
    } else if (id == 6) { // 最小边界
        pattern = "z";
        words = {"apple"};
    } else if (id <= 8) { // 最大规模 True (id 7,8)
        int n = 300;
        vector<string> dict;
        for(int i=0; i<n; ++i) dict.push_back(gen_word(5)); // 每个单词5字，总长约1800 < 3000
        for(int i=0; i<n; ++i) {
            char c = (char)('a' + (i % 26));
            pattern += c;
            // 为了保证 True，需要确保相同的 c 对应相同的单词
            // 这里我们简化处理，让每个位置都不一样
            words.push_back(dict[i]); 
            // 注意：如果 i%26 重复，我们需要修正 words 让其符合双射
        }
        // 修正：重新构建符合逻辑的 pattern 和 words
        pattern = ""; words.clear();
        map<char, string> fixed_map;
        for(int i=0; i<n; ++i) {
            char c = (char)('a' + (rng() % 26));
            pattern += c;
            if(fixed_map.count(c)) words.push_back(fixed_map[c]);
            else {
                string new_w = gen_word(8);
                fixed_map[c] = new_w;
                words.push_back(new_w);
            }
        }
    } else { // 混合随机 (id 9,10)
        int n = 150 + rng() % 150;
        for (int i = 0; i < n; ++i) pattern += (char)('a' + rng() % 26);
        for (int i = 0; i < n; ++i) words.push_back(gen_word(4));
    }

    // 将 words 组合成字符串 s
    for (int i = 0; i < (int)words.size(); ++i) {
        s += words[i];
        if (i != (int)words.size() - 1) s += " ";
    }

    // 限制 s 长度不超过 3000 (针对随机生成的简单截断)
    if (s.length() > 3000) s = s.substr(0, 3000); 

    fout << pattern << endl;
    fout << s << endl;
    fout.close();

    // 生成答案
    ofstream fans(out_name);
    fans << solve(pattern, s) << endl;
    fans.close();
    cout << "Test Case " << id << " Generated." << endl;
}

int main() {
    for (int i = 1; i <= 10; ++i) {
        make_data(i);
    }
    return 0;
}

三、 优化与防错思考

1. 分词性能： 数据生成器中使用了 stringstream 进行分词。虽然在极大规模下（如 $10^6$）它可能稍慢，但在本题 $M=3000$ 的规模下，其处理速度在毫秒级，不会导致生成超时。
2. 避免除零： 代码中唯一涉及取模的操作是 rng() % 26 和 rng() % n。由于除数均为固定正整数或经过范围限定的正数，不存在除以 0 的风险。
3. 栈溢出防御： 本题的逻辑（双射判定）是线性的，不涉及任何深层递归或图论遍历，因此不存在爆栈风险。
4. IO 缓冲区说明： getline(cin >> ws, s) 是竞赛中读取 pattern 之后读取带空格字符串的常用技巧。ws 算子会自动跳过 cin >> pattern 留在缓冲区里的回车符。
5. 数据有效性： 在 id=7,8 的生成逻辑中，我特别注意了如果 pattern 中出现了相同的字符，对应的单词必须相同才能生成 true 的样例。这保证了测试数据中既有高质量的 true 也有高质量的 false。

四、 如何在 OJ 使用

1. 编译运行此生成器，得到 1.in/out ~ 10.in/out。
2. 将 pattern 长度设定为 $300$，s 长度设定为 $3000$ 的上限。
3. 测评时，注意 C++ 的 cin >> pattern 后面紧跟 getline 时，务必提醒选手处理掉中间的换行符（这是本题最常见的选手失分点）。

这道题在字符串模拟中非常经典，主要考察对**双射（One-to-One Correspondence）**逻辑的严谨实现。在 NOI 竞赛中，这类题目通常作为签到题或初级模拟题出现。

一、 Word Pattern 标准题解 (C++14)

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

using namespace std;

/**
 * 判定函数：判定 pattern 与 s 是否满足双射关系
 */
bool check_word_pattern(const string& pattern, const string& s) {
    vector<string> words;
    stringstream ss(s);
    string temp;
    
    // 1. 将字符串 s 按空格切分为单词序列
    // 易错点：如果 s 结尾有冗余空格，需确保切分逻辑的鲁棒性
    while (ss >> temp) {
        words.push_back(temp);
    }
    
    // 2. 数量校验
    // 易错点：如果 pattern 长度与单词数量不等，必然不符合规律
    if (pattern.length() != words.size()) {
        return false;
    }
    
    // 3. 建立双向映射
    // p2s: 字符 -> 单词
    // s2p: 单词 -> 字符
    map<char, string> p2s;
    map<string, char> s2p;
    
    for (int i = 0; i < (int)pattern.length(); ++i) {
        char ch = pattern[i];
        string word = words[i];
        
        // 检查 正向映射：字符 ch 是否已经映射到了别的单词
        if (p2s.count(ch)) {
            if (p2s[ch] != word) return false;
        } else {
            p2s[ch] = word;
        }
        
        // 检查 反向映射：单词 word 是否已经由别的字符映射过来
        // 易错点：漏掉反向判定会导致 "abba" -> "dog dog dog dog" 判定为 true
        if (s2p.count(word)) {
            if (s2p[word] != ch) return false;
        } else {
            s2p[word] = ch;
        }
    }
    
    return true;
}

int main() {
    // 优化 I/O 效率
    ios::sync_with_stdio(false);
    cin.tie(0);

    string pattern, s;
    
    // 读取 pattern
    if (!(cin >> pattern)) return 0;
    
    // 易错点：cin >> pattern 后缓冲区留有换行符，需使用 ws 跳过空白字符后再 getline
    // 或者先 getchar() 消耗掉换行符
    getline(cin >> ws, s);
    
    if (check_word_pattern(pattern, s)) {
        cout << "true" << endl;
    } else {
        cout << "false" << endl;
    }
    
    return 0;
}

二、 复杂度分析思考过程

1. 时间复杂度分析

• 分词阶段：stringstream 遍历一次字符串 $s$，复杂度为 $O(M)$，其中 $M$ 为 $s$ 的长度。
• 匹配阶段：遍历 pattern，长度为 $N$。
  • 在 map 中进行查找和插入操作，复杂度为 $O(\log K \times L)$，其中 $K$ 是去重后的单词/字符数，$L$ 是字符串的平均长度。
• 总体复杂度：$O(M + N \cdot L \cdot \log K)$。
  • 在本题规模下（$N=300, M=3000$），由于 $N \cdot L \approx M$，整体复杂度接近 $O(M \log K)$。这在 1s 限制内绰绰有余（哪怕 $M=10^5$ 也能跑过）。

2. 空间复杂度分析

• 存储开销：vector<string> 存储了所有的单词，空间为 $O(M)$。
• 映射表开销：两个 map 存储了字符与单词的对应关系，最坏情况下空间也为 $O(M)$。
• 结论：总空间复杂度 $O(M)$。

三、 时间复杂度优化建议

1. 哈希表优化： 将 std::map 替换为 std::unordered_map。std::map 底层是红黑树（$O(\log n)$），而 unordered_map 是哈希表（平均 $O(1)$）。对于大规模数据，哈希表能显著减少常数项开销。

2. 空间换时间（针对字符映射）： 由于 pattern 仅包含小写字母，可以使用一个固定长度为 26 的数组 string char_to_word[26] 来替代正向映射 map。

   string p2s[26];
   bool used_p[26] = {false};
   // ... 在循环中 ...
   int idx = ch - 'a';
   if(used_p[idx]) {
       if(p2s[idx] != word) return false;
   } else {
       p2s[idx] = word;
       used_p[idx] = true;
   }
   

3. 单次遍历分词： 不使用 stringstream 或 vector<string>，而是直接在遍历 pattern 的过程中，利用双指针动态地从 $s$ 中截取单词。这可以节省存储单词列表所需的内存空间。

四、 读题理解关键词总结

在 NOI 字符串类题目中，看到以下表述需立即警觉：

1. “遵循相同的规律”：通常指结构上的同构或映射关系。
2. “每个...对应一个...”：这是映射的定义。一定要注意是单向映射还是双向映射（双射）。
   • 如果题目说“A 对应 B”，不代表“B 只能对应 A”。
   • 如果题目说“一一对应”，则必须写双向哈希比对。
3. “非空单词”与“单个空格”：这是模拟分词的边界条件。如果题目说“单词间可能有多个空格”，则不能使用简单的固定偏移量寻找单词，必须用 while(s[i] == ' ') i++; 来跳过空白。
4. 数据规模 (300, 3000)：这么小的规模暗示你可以使用常数略大但更安全的 std::map 或 std::string 操作，而不需要过早进行复杂的位运算优化。