[语言月赛202304] 写大作业 - 计算理论大作业的字符串相似性判断 - 常规

题目描述

扶苏为了写计算理论大作业已经 36 小时没有合眼了。

为了能快点睡觉，扶苏找到了 n 份文献，第 i 份文献是一个字符串 s_i，她打算把这些文献组合起来。

具体来说，一共有两种操作：

'1 x y'：把文献 s_x 整体拼接到 s_y 的后面，然后删除 s_x。
'2 x y'：查询 s_x 和 s_y 是否'相似'。

我们保证在 '1 x y' 操作出现后，字符串 s_x '不会'出现在接下来的任何操作中。这就是说，操作 1 至多有 n-1 次。

'相似'的定义是：对两个字符串 s_x 和 s_y，如果存在一种重新排列 s_x 的方法，使得重排后的 s_x 和 s_y 相等，则称 s_x 和 s_y '相似'。

例如，假设 s_1 = 'ab', s_2 = 'cd', s_3 = 'abcd'，则执行 '1 1 2' 后，s_1 被删除，s_2 = 'cdab', s_3 = 'abcd'；继续执行 '2 2 3' 后，因为可以把 s_2 重排为 'abcd'，所以 s_2 和 s_3 相似。

注意，操作 2 不会对字符串做出实际修改。

输入格式

第一行是两个整数，分别表示文献的数量 n 和操作的数量 q。
接下来 n 行，每行一个字符串，第 i 行的字符串表示 s_i。
接下来 q 行，每行三个整数 op, x, y，其含义见『题目描述』。

输出格式

对个操作 2，输出一行一个字符串。如果 s_x 和 s_y 相似，则输出 'Yes'，否则输出 'No'。

样例 #1

样例输入 #1

4 4
ab
cd
abcd
abcc
1 1 2
2 2 3
2 3 4
2 2 4

样例输出 #1

Yes
No
No

提示

数据规模与约定

对 30% 的数据，保证 n = 2，q = 1。
对 60% 的数据，保证 n ≤ 6，q ≤ 6，|s_i| ≤ 6。
对 100% 的数据，保证 2 ≤ n ≤ 10^5，1 ≤ q ≤ 10^6，1 ≤ o ≤ 2，1 ≤ x, y ≤ n，且输入字符串的总长度不超过 10^6，输入字符串仅含小写英文字母，且不是空串。用C++,时间复杂度为O(n + q)内容：### 思路解析

首先我们需要明确一下题目中的操作1和操作2的具体含义：

操作1：将文献 s_x 拼接到文献 s_y 的后面，并删除文献 s_x。
操作2：判断文献 s_x 和文献 s_y 是否相似。

我们可以使用哈希表来记录每个字符串中每个字符出现的次数。对于每个操作2，我们只需要比较两个字符串的哈希表是否相同即可判断它们是否相似。

具体的实现过程如下：

初始化一个空的哈希表 unordered_map<string, unordered_map<char, int>> m，用来记录每个字符串中每个字符出现的次数。
遍历每个文献，将每个字符串的字符出现次数记录到哈希表中。
遍历每个操作，根据操作类型执行相应的操作：
- 如果是操作1，将文献 s_x 的字符出现次数加到文献 s_y 中，并将文献 s_x 从哈希表中删除。
- 如果是操作2，比较文献 s_x 和文献 s_y 的哈希表是否相同，如果相同输出 'Yes'，否则输出 'No'。

代码实现

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;

    // 初始化哈希表
    unordered_map<string, unordered_map<char, int>> m;

    // 读取每个文献，记录字符出现次数
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (char c : s) {
            m[s][c]++;
        }
    }

    // 处理每个操作
    for (int i = 0; i < q; i++) {
        int op, x, y;
        cin >> op >> x >> y;

        if (op == 1) {
            // 将文献 x 的字符出现次数加到文献 y 中
            for (auto it : m[to_string(x)]) {
                m[to_string(y)][it.first] += it.second;
            }
            // 删除文献 x
            m.erase(to_string(x));
        } else if (op == 2) {
            // 比较文献 x 和文献 y 的字符出现次数
            if (m[to_string(x)] == m[to_string(y)]) {
                cout << 'Yes' << endl;
            } else {
                cout << 'No' << endl;
            }
        }
    }

    return 0;
}

复杂度分析

时间复杂度：对于每个操作，都需要遍历操作涉及的字符串中的字符，因此总的时间复杂度为 O(n + q)。
空间复杂度：使用了一个哈希表来记录每个字符串中每个字符出现的次数，因此空间复杂度为 O(n ⋅ m)，其中 m 是字符串的平均长度。