[语言月赛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，输入字符串仅含小写英文字母，且不是空串。

解题思路

对于每个字符串，我们可以使用一个数组来记录每个字符出现的次数。具体来说，我们可以使用一个大小为26的数组freq来记录每个小写字母出现的次数。那么对于字符串s，我们可以遍历字符串中的每个字符c，然后将c-'a'作为下标，将freq[c-'a']的值加1。这样，我们就可以通过freq数组来比较两个字符串是否相似了。

具体的步骤如下：

初始化一个二维数组freq，大小为n*26，用于记录每个字符串中每个字符出现的次数。
初始化一个大小为n的数组length，用于记录每个字符串的长度。
遍历每个字符串，对于第i个字符串，进行以下操作：
- 初始化一个大小为26的数组count，用于记录当前字符串中每个字符出现的次数。
- 遍历字符串中的每个字符，对于字符c，将count[c-'a']的值加1。
- 将count数组中的值复制到freq[i]中。
- 将字符串的长度保存在length[i]中。
遍历每个操作，对于每个操作，进行以下判断：
- 如果操作为1，则将字符串s[x]的freq[x]数组与字符串s[y]的freq[y]数组相加，并将字符串s[x]的freq[x]数组清零。
- 如果操作为2，则判断字符串s[x]和字符串s[y]是否相似。具体来说，我们可以通过比较freq[x]和freq[y]数组中的值来判断两个字符串是否相似。如果两个数组完全相同，则说明两个字符串相似，否则不相似。

复杂度分析

该算法的时间复杂度为O(n+q)，其中n为字符串的数量，q为操作的数量。算法的空间复杂度为O(n*26)，用于存储每个字符串中每个字符出现的次数。