P8270 [USACO22OPEN] Subset Equality S 题解
tzyt
2022-04-10 10:25:36
update： 2022/4/17 更正了博客地址
[题目连接](https://www.luogu.com.cn/problem/P8270)
[博客](https://ttzytt.com/2022/04/P8270/)中观看体验更佳
# 1：题意
给你两个字符串，$s$ 和 $t$ （ $s$ 和 $t$ 的长度都不超过 $10^5$ ）。再给你一些询问 （ 询问数量不超过 $10^5$ ），每个询问为小写字母 `'a'` 到 `'r'` 的子集，对于每个询问，请你回答在 $s$ 串和 $t$ 串只包含询问中给定的字母时是否相等。
# 2：分析
## 2.1：暴力
很容易想到暴力的方法，对于每个询问，我们可以只考虑包含在集合中的字符，然后对比两个字符串。当然，这样我们就会需要对于每个询问重新遍历一遍字符串，复杂度也会到达 $n^2$ （ $n$ 为询问的数量和字符串的长度）。通过这个方法，我们可以拿到这道题的部分分。
不过如何才能拿到其他分数呢？
## 2.2：简化问题
直接解决这个问题可能太复杂了，我们可以试试看化简一下这个问题，再把化简过的解法推广到原问题。
我们首先考虑询问中只包含两个字母的情况。设这两个字母为 a 和 b。那么我们如何判断两个只包含 a 和 b 的字符串是否相等呢？
首先需要考虑的肯定是两个串中 a 和 b 的数量是否相等，如果 a 和 b 的数量不等，那这两个串一定不一样。
其次，我们得考虑字符串中每个 a 和 b 的位置，如果位置和数量都对了，这两个串就一定相等了。
判断 a 和 b 的位置时，我们肯定不能直接看它们的下标是否相等，因为我们比较的是这两个字符串中只包含 a 和 b 时的位置，而把其他字符删除后，它们的下标一定会变化。
删除其他字符后，每个字符串的下标其实就是它前面 a 的数量加上 b 的数量（其他的字符都被删除了）。
当然，依次判断每个 a 和 b 的下标太废时间了，我们可以做一些优化。比如我们只需要判断 a 和 b 中一个字符的位置是否全部相等就行了。因为两个字符串 a 和 b 的数量相等，所以只要确定了其中一个字符的位置，另一个的就能确定了（所有不是 a 的位置肯定都是 b）。
这个判断过程其实还可以进一步简化，我们可以只考虑 a 前面 b 的数量，考虑这样一个字符串: `"baa"` 。可以发现如果把 a 前面 b 的数量当作 a 的下标，那么这两个 a 的下标都是一样的。如果我们交换这两个 a，这个字符串还是一样的，所以这两个 a 的下标一样并不会对我们判断 a 的位置产生影响。
总结一下，只包含两个字符的字符串（假设这两个字符为 a 和 b），如果是相等的，一定满足：
- a 和 b 的数量相等
- 每个 a 前面 b 的数量相等
----
可是我们为什么要用这样的方法求字符串是否相等呢？
因为通过前缀和的方法，我们可以很快的速度处理出这两个字符串只包含两个字符时是否相等。
考虑前文中提到的两个条件。要求出每个 a 前面 b 的数量是否相等（注意这里的 a 和 b 可以是任何字符），我们需要快速求出：
- 原串中每个位置前面每种字符的数量。
- 原串种每种字符的位置（所有位置）
对于第一个问题，我们可以使用前缀和来预处理。
我们开两个数组 `char_sum_s[i][j]` 和 `char_sum_t[i][j]`，分别表示在串 $s$ 和 $t$ 中，从下标 $0$ 到下标 $i$ 为止（包括 $i$）有多少个字符 $j$。
然后使用下面这段代码求出：
```cpp
for(int i = 0; i < s.length(); i++){
char_sum_s[i][s[i] - 'a'] = 1; // 打上标记
}
for(int i = 1; i < s.length(); i++){
for(int j = 0; j < 20; j++){ // 枚举字符
char_sum_s[i][j] += char_sum_s[i - 1][j]; // 求前缀和
}
}
```
对于第二个问题，我们开两个 vector `char_pos_s[i]` 和 `char_pos_s[i]`， 分别表示串 $s$ 和 $t$ 中，字符 $i$ 的所有位置，并且使用下面的代码求出：
```cpp
for(int i = 0; i < s.length(); i++){
char_pos_s[s[i] - 'a'].push_back(i);
}
```
## 2.3：考虑原问题
现在我们已经能快速求出只包含两个字符时两个串是否相等了，下面我们来考虑如何把它用到原问题中。
假设两串原本是一样的，有下面几种方法使它们变得不一样：
- 增加字符
- 删除字符
- 交换字符（两个相同字符交换等于没交换）
注：为了方便，我们把判断两字符串在只包含字符 a , b 时是否相等的函数记为 `isok(a, b)`
对于前面两种改变方式，两串中每种字符的数量肯定会改变。假设增加或删除的字符为 a，那么 `isok(a, 其他任何字符)` 返回的一定是 `false`，这是因为在 $s$ 串中和 $t$ 串中，字符 a 的数量不相等了。
现在考虑交换这种改变方式，假设交换的字符为 a 和 b， 那么 `isok(a, b)` 返回的也一定是 `false`。因为在 $s$ 和 $t$ 中，仅由 a 和 b 组成的字符串一定不相等。
所以，对于每个询问，我们只需要枚举询问中包括的两个不同的字符，然后判断 $s$ 串和 $t$ 串在只包含这两种字符时是否相等就可以了。
注意我们需要把每个 `isok(a, b)` 的结果存下来，这样下此使用时就不需要重新算了。
## 2.3：复杂度分析
- **预处理**： $O(n)$
- **`isok(a, b)`** ：因为需要知道每个 a 前面 b 的数量，所以需要枚举 a，复杂度就为 a 的数量。
- **处理所有 `isok(a, b)`** ： $O(n)$（ $n$ 为字符串长度） 因为要枚举所有的 a 和 b 来计算 `isok(a, b)` ，而所有的 a 和 b 的数量和一定是字符串长度。
- **询问**：$\text{一次询问中字母的数量}^2 \times \text{询问数量}$，因为已经处理过所有的 `isok(a, b)` 了，所以在枚举枚举询问中包括的两个不同的字符时，只需要返回结果，复杂度为 $O(1)$。而一共要枚举 $\text{一次询问中字母的数量}^2$ 次。
# 3：代码
有详细注释，相对来说还是比较快的，[提交记录](https://www.luogu.com.cn/record/73616097)。
```cpp
/*Date: 22 - 03-26 16 22
PROBLEM_NUM: Subset Equality*/
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
string s, t;
int q;
vector<int> char_pos_s[20], char_pos_t[20];
int char_sum_s[MAXN][20], char_sum_t[MAXN][20];
short isok_result[20][20];
bool ans[MAXN];
bool isok(char a, char b){// 判断 s 和 t 串在只包含 a 和 b 的情况下是否等价
if(isok_result[a][b] != -1 || isok_result[b][a] != -1){// 如果之前已经计算过了，直接返回结果，注意 isok(a, b) == isok(b, a)
return isok_result[a][b];
}
if(a == b){// 如果 a 和 b 相等，则返回这个字符在两串中出现的次数是否相等
return isok_result[a][b] = (char_pos_s[a].size() == char_pos_t[a].size());
}
if(char_pos_s[a].size() != char_pos_t[a].size() || char_pos_s[b].size() != char_pos_t[b].size()){// 如果 a 和 b 的个数在 s 串和 t 串中不相等，返回 false
return isok_result[a][b] = false;
}
vector<int> b_cnt_s;//s串中，某个 a 前面的 b 的数量
for(int cur_apos : char_pos_s[a]){ // 枚举 s 串中 a 的位置
b_cnt_s.push_back(char_sum_s[cur_apos][b]);
}
for(int i = 0; i < char_pos_t[a].size(); i++){// 枚举 t 串中 a 的位置，对比 t 串中 a 前面 b 的
// 数量是否和 s 串中 a 前面的 b 的数量相等
if(char_sum_t[char_pos_t[a][i]][b] != b_cnt_s[i]){
return isok_result[a][b] = false;
}
}
return isok_result[a][b] = true;
}
void pre_proc(){
for(int i = 0; i < s.length(); i++){
char_pos_s[s[i] - 'a'].push_back(i);
char_sum_s[i][s[i] - 'a'] = 1; // 打标记
}
for(int i = 0; i < t.length(); i++){
char_pos_t[t[i] - 'a'].push_back(i);
char_sum_t[i][t[i] - 'a'] = 1;
}
for(int i = 1; i < s.length(); i++)// s 串前缀和
for(int j = 0; j < 20; j++)
char_sum_s[i][j] += char_sum_s[i - 1][j];
for(int i = 1; i < t.length(); i++)// t 串前缀和
for(int j = 0; j < 20; j++) // j 为字符
char_sum_t[i][j] += char_sum_t[i - 1][j];
for(int i = 0; i < 20; i++)
for(int j = 0; j < 20; j++)
isok_result[i][j] = -1;// 没计算过的时候，设置为 -1
}
int main(){
ios::sync_with_stdio(false);
cin>>s>>t>>q;
pre_proc();// 预处理
for(int i = 1; i <= q; i++){// 枚举每个询问中的每个字符
string cur_query;
cin>>cur_query;
ans[i] = true;
for(char char_a : cur_query){
for(char char_b : cur_query){
if(!isok(char_a - 'a', char_b - 'a')){ // 如果有一个 isok(a, b) == false，则说明不等价
//（当 s 和 t 只包含询问中的字符时）
ans[i] = false;
break;
}
}
if(!ans[i]) break;
}
}
for(int i = 1; i <= q; i++){
if(ans[i])
cout<<"Y";
else
cout<<"N";
}
system("pause");
}
```
最后希望这篇题解能帮到你。如果有看不懂的，或者是发现题解有问题，欢迎通过评论区和私信联系我。