Subset Equality (USACO Silver 2022 Open)

Subset Equality (USACO Silver 2022 Open)

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

  1. count[2][x]，字母x的个数
  2. mismatch(x,y), 字母x和y存在“错位”

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

  1. 所有字母的个数得一致。
  2. 两两之间不存在错位（最多18*18/2个字母对）
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int q, slen, tlen;
char s[100005];
char t[100005];
 
int cnt[2][20];
bool mis[20][20];       // mismatches between letter pairs
 
int main() {
    scanf("%s", s);
    scanf("%s", t);
    slen = strlen(s);
    tlen = strlen(t);
 
    // 预处理count
    for (int i = 0; i < slen; i++)
        cnt[0][s[i]-'a']++;
    for (int i = 0; i < tlen; i++)
        cnt[1][t[i]-'a']++;
    // 预处理mismatch: two pointers
    int pos[20][20] = {0};      // position of each {x,y} letter pair sub-stream in t
    for (int i = 0; i < slen; i++) {
        char a = s[i];
        for (char b = 'a'; b <= 'r'; b++) {
            if (a == b) continue;
            int x = min(a,b)-'a', y = max(a,b)-'a';
            if (mis[x][y]) continue;   // already in mismatch
            // if we find b instead of a as next char in t, we have mismatched
            while (pos[x][y] < tlen && t[pos[x][y]] != a && t[pos[x][y]] != b)
                pos[x][y]++;
            if (pos[x][y] == tlen || t[pos[x][y]] == b)
                mis[x][y] = true;
            else
                pos[x][y]++;
        }
    }
 
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        char p[20];
        scanf("%s", p);
        int plen = strlen(p);
        bool ok = true;
        for (int i = 0; i < plen; i++)
            if (cnt[0][p[i]-'a'] != cnt[1][p[i]-'a']) {
                ok = false;
                break;
            }
        if (ok) {
            // check all letter pairs for mismatches
            for (int i = 0; i < plen; i++) {
                for (int j = i+1; j < plen; j++)
                    if (mis[p[i]-'a'][p[j]-'a']) {
                        ok = false;
                        break;
                    }
                if (!ok) break;
            }
        }
 
        printf(ok ? "Y" : "N");
    }
 
    return 0;
}