Subset Equality (USACO Silver 2022 Open)

一遍扫描预处理两个数据结构：

cnt[2][x]，字母x的个数
mis(x,y), 字母x和y存在“错位”

有了这两个数据结构之后，就可以快速回答每个query了

所有字母的个数得一致。
两两之间不存在错位（最多18*18/2个字母对）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int q, n;
string s, t;
string s0, t0;
int cnt[2][20];
bool mis[20][20];
 
int main() {
    cin >> s; 
    cin >> t;
    for (char c : s) cnt[0][c-'a']++;
    for (char c : t) cnt[1][c-'a']++;
 
    for (int i = 0; i < 18; i++) {
        for (int j = 0; j < 18; j++) {
            s0.clear(); t0.clear();
            for (char c : s) if (c == 'a'+i || c == 'a'+j) s0 += c;
            for (char c : t) if (c == 'a'+i || c == 'a'+j) t0 += c;
            if (s0 != t0) mis[i][j] = true;
        }
    }
 
    cin >> q;
    for (int i = 0; i < q; i++) {
        string p;
        cin >> p;
        bool ok = true;
        for (char c : p)
            if (cnt[0][c-'a'] != cnt[1][c-'a']) {
                ok = false; break;
            }
        for (char c : p)
            for (char d : p)
                if (c != d && mis[c-'a'][d-'a']) {
                    ok = false; break;
                }
        cout << (ok ? "Y" : "N");
    }
    return 0;
}