模板生成系统

GitHub跳转原题关系图Canvas 关系图返回列表

扫描模板中的 {{ VAR }} 标记，用变量表中的值做一次非递归替换。

OJ: shumeng

题目 ID: CSP201509C

难度:入门

标签:字符串模拟

日期: 2026-07-31 16:21

目录

  1. 形式化题目
  2. 思路
    1. 关键点：不递归
  3. 代码
  4. 复杂度
  5. 总结

形式化题目

给定 mm 行模板和 nn 个形如 名称 "值" 的变量定义。模板中出现的标记 {{ VAR }} 会被变量 VAR 的值替换；未定义的变量替换为空串。替换结果不再递归处理，即变量值里若再出现 {{ ... }} 不会再次替换。

思路

读入变量定义后存入映射表，然后逐行扫描模板。扫描时维护当前下标 i：

  1. 若当前位置不是标记开头，直接复制该字符，i 前进一位；
  2. 若当前位置是 {{ ，则向后找到 }}，取出中间的变量名，拼接其映射值，i 跳到 }} 之后；
  3. 重复直到处理完当前行。

关键点：不递归

每个标记都只从原模板读取一次。变量值中的内容只是被拼进答案字符串，不再作为模板被扫描，因此自然满足“模板不递归生成”。

代码

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:56
 */
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m, n;
    cin >> m >> n;
    string line;
    getline(cin, line); // 吃掉第一行末尾的换行符
    vector<string> templ(m); // 模板的每一行
    for (int i = 0; i < m; i++) getline(cin, templ[i]);

    // 变量表：变量名 -> 变量值（值形如 "xxx"，去掉两侧双引号）。
    map<string, string> values;
    for (int i = 0; i < n; i++) {
        getline(cin, line);
        int split = line.find(' ');
        values[line.substr(0, split)] = line.substr(split + 2, line.size() - split - 3);
    }

    // 逐行扫描模板：普通字符直接复制，遇到 {{ 标记则替换为变量值。
    for (int row = 0; row < m; row++) {
        string answer;
        for (int i = 0; i < (int)templ[row].size();) {
            if (i + 2 < (int)templ[row].size() && templ[row].substr(i, 3) == "{{ ") {
                int end = templ[row].find(" }}", i + 3);
                string name = templ[row].substr(i + 3, end - i - 3);
                answer += values[name]; // 未定义变量自动得到空串
                i = end + 3;
            } else {
                answer += templ[row][i];
                i++;
            }
        }
        cout << answer << '\n';
    }
    return 0;
}

复杂度

设模板总长度为 LL，变量数为 nn。

  • 时间：每个字符最多被扫描一次，O(L)O(L)；每次查表 O(log⁡n)O(\log n)，总时间 O(Llog⁡n)O(L\log n)。
  • 空间：存储模板与变量表，O(L+n)O(L + n)。

总结

模板替换要区分“原文本”和“已经输出的变量值”。始终扫描原模板，输出的内容一律不再检查，就能保证“不递归生成”这个约束被自然满足。