E. Funny Substrings - 题解

比赛与标签

比赛: Codeforces Round 725 (Div. 3) 标签: data structures, hashing, implementation, matrices, strings 难度: *2100

这道题是想让我们做什么喵？

主人你好呀~ 这道题呀，是让我们模拟一个超级简单的编程语言！这个语言里只有两种操作：

1. 赋值操作 (x := s): 就是把一个字符串 s 直接交给一个叫 x 的变量。很简单对吧，喵~
2. 拼接操作 (x = a + b): 把变量 a 和变量 b 的字符串拼在一起，然后把结果交给变量 x。比如 a 是 "nyaa" b 是 "meow"，那么 x 就变成了 "nyaameow" 啦！

我们的任务呢，就是在所有操作都执行完之后，计算最后一个被赋值的变量里，出现了多少次 "haha" 这个可爱的字符串！

听起来好像只要模拟一下就好了？但是主人请注意！题目里的拼接操作可能会执行很多次，字符串会变得超级——超级——长！要是真的把整个字符串都存下来，肯定会把内存撑爆或者超时（TLE/MLE）的，那可就糟啦！所以，我们需要更聪明的办法，喵~

聪明的猫娘是如何思考的喵~

既然不能硬来，那我们就要动动我们的小脑袋瓜啦！我们的目标只是数 "haha" 的数量，并不真的需要完整的字符串，对不对？

想象一下，当我们要计算 c = a + b 时，c 里面的 "haha" 是从哪里来的呢？

1. 原来就在 a 里面的 "haha"。
2. 原来就在 b 里面的 "haha"。
3. 最关键的一点！ 在 a 的末尾和 b 的开头拼接处，新产生的 "haha"！

举个例子，如果 a 是 "hah"，b 是 "aha"，那么 c 就是 "hahaha"。a 和 b 本身都没有 "haha"，但是它们一结合，就在中间创造了一个 "haha"！

所以，我们只需要知道每个变量包含的 "haha" 数量，以及它们拼接时能不能产生新的 "haha" 就行了。

那怎样才能判断拼接时会不会产生新的 "haha" 呢？"haha" 的长度是4，所以新产生的 "haha" 一定是由 a 的末尾几个字符和 b 的开头几个字符组成的。具体来说，有这几种可能：

• a 的结尾是 "h"，b 的开头是 "aha"
• a 的结尾是 "ha"，b 的开头是 "ha"
• a 的结尾是 "hah"，b 的开头是 "a"

我们发现，为了判断所有可能的情况，我们最多只需要知道 a 的最后3个字符和 b 的最前3个字符！更多就不需要了，因为 "haha" 只有4个字符长嘛。

叮！灵光一闪！ 这就是我们的解题秘诀喵！对于每一个变量，我们不需要存储它那长得吓人的完整字符串，我们只需要维护这三样东西：

1. haha_count: 变量当前字符串中已经包含的 "haha" 的总数。
2. prefix: 变量字符串的前3个字符（如果字符串长度不足3，就存整个字符串）。
3. suffix: 变量字符串的后3个字符（如果字符串长度不足3，也存整个字符串）。

有了这三件法宝，我们就可以处理所有操作啦！

• 对于赋值操作 x := s:

  • haha_count: 直接数一下字符串 s 里有多少个 "haha"。
  • prefix: 取 s 的前3个字符。
  • suffix: 取 s 的后3个字符。

• 对于拼接操作 x = a + b:

  • haha_count: 新的总数 = a 的 haha_count + b 的 haha_count + 在拼接处新产生的 "haha" 数量。这个新产生的数量，可以通过计算 a 的 suffix 和 b 的 prefix 拼接起来的字符串 (a.suffix + b.prefix) 中 "haha" 的数量得到。
  • prefix: 新的 prefix 是 a.prefix + b.prefix 的前3个字符。
  • suffix: 新的 suffix 是 a.suffix + b.suffix 的后3个字符。

这样一来，无论原来的字符串有多长，我们每个变量都只需要存储很小量的信息。是不是超级高效又优雅呢？喵~ 我们可以用一个 map 来存储每个变量名和它对应的这三样信息。

代码魔法，变身喵！

下面就是把我们的思路变成代码的时刻啦！看我的代码魔法！

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

// 一个小小的工具函数，专门用来数 "haha" 的说~
long long count_haha(const std::string& s) {
    long long count = 0;
    for (size_t i = 0; (i = s.find("haha", i)) != std::string::npos; ++i) {
        count++;
    }
    return count;
}

// 这就是我们为每个变量准备的“信息包”喵！
struct VarInfo {
    long long haha_count = 0; // 存储haha的数量
    std::string prefix;       // 存储前缀（最多3个字符）
    std::string suffix;       // 存储后缀（最多3个字符）
};

void solve() {
    int n;
    std::cin >> n;
    std::string dummy;
    std::getline(std::cin, dummy); // 吃掉n后面的换行符，防止捣乱喵

    // 用一个map来管理所有变量的信息，名字到信息的映射！
    std::map<std::string, VarInfo> vars;
    std::string last_var; // 记录最后一个被操作的变量名

    for (int i = 0; i < n; ++i) {
        std::string line;
        std::getline(std::cin, line);
        std::stringstream ss(line); // stringstream是解析字符串的好帮手！
        std::string var, op;
        ss >> var >> op;
        last_var = var; // 更新最后一个变量名

        if (op == ":=") { // 这是赋值操作
            std::string val;
            ss >> val;
            vars[var].haha_count = count_haha(val);
            // 如果字符串太短，前缀后缀就是它自己
            if (val.length() <= 3) {
                vars[var].prefix = val;
                vars[var].suffix = val;
            } else { // 否则就截取前3和后3
                vars[var].prefix = val.substr(0, 3);
                vars[var].suffix = val.substr(val.length() - 3);
            }
        } else { // 这是拼接操作 (op is "=")
            std::string v1, plus, v2;
            ss >> v1 >> plus >> v2;
            
            VarInfo& info1 = vars[v1];
            VarInfo& info2 = vars[v2];
            
            // 关键一步！检查边界处新生成的"haha"
            std::string combined_boundary = info1.suffix + info2.prefix;
            long long boundary_hahas = count_haha(combined_boundary);
            
            // 新的haha总数 = a的 + b的 + 边界新增的
            vars[var].haha_count = info1.haha_count + info2.haha_count + boundary_hahas;
            
            // 更新新的前缀
            std::string new_prefix_str = info1.prefix + info2.prefix;
            if (new_prefix_str.length() > 3) {
                vars[var].prefix = new_prefix_str.substr(0, 3);
            } else {
                vars[var].prefix = new_prefix_str;
            }

            // 更新新的后缀
            std::string new_suffix_str = info1.suffix + info2.suffix;
            if (new_suffix_str.length() > 3) {
                vars[var].suffix = new_suffix_str.substr(new_suffix_str.length() - 3);
            } else {
                vars[var].suffix = new_suffix_str;
            }
        }
    }
    // 最后，输出我们追踪的最终答案！
    std::cout << vars[last_var].haha_count << std::endl;
}

int main() {
    // 加速输入输出，让程序跑得飞快喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

性能分析时间到~

• 时间复杂度: O(N * logN) 的说。 在一个测试用例中，有 N 条语句。对于每一条语句，我们做的操作主要是：解析字符串（很快）、在 map 中查找变量（O(logV)，V是变量数量，最多为N）、以及一些字符串操作。字符串操作（如 substr, +）的对象都是长度不超过3+3=6的短字符串，所以是常数时间。因此，处理一条语句的复杂度是 O(logN)，总复杂度就是 O(N * logN) 啦，非常快！

• 空间复杂度: O(N) 的说。 我们需要一个 map 来存储所有变量的信息。最多有 N 个不同的变量，每个变量的 VarInfo 结构占用的空间是固定的（一个 long long 和两个短 string）。所以总空间复杂度和变量数量成正比，也就是 O(N)。完全不用担心内存问题！

猫娘的小课堂时间~

这道题真是太有趣啦，它教会了我们一个非常重要的思想，喵~

• 核心思想: 这种方法可以叫做 状态压缩 或者 动态规划 的一种应用。我们没有傻乎乎地去维护一个可能会无限增长的庞然大物（完整的字符串），而是提炼出了对未来计算有用的 最小状态 —— {haha_count, prefix, suffix}。只维护必要的信息，是解决这类问题的制胜法宝！

• 关键点: 正确地识别出需要维护哪些信息是解题的关键。在这里，因为我们要找的模式串 "haha" 长度为4，所以长度为 4-1=3 的前后缀信息就足够了。如果我们要找的是其他长度为 L 的字符串，那我们可能就需要维护长度为 L-1 的前后缀了哦。

• 实用小技巧:

  • std::map 在需要通过名字（字符串）来查找对应数据时非常好用。
  • std::stringstream 是C++里处理格式化输入行的神器，能让代码变得更整洁。

希望这篇题解能帮到主人哦！只要抓住了问题的本质，再复杂的题目也能被我们轻松解决的！继续加油，向着算法大师的目标前进吧，喵~！