毛毛的密码

形式化题目

两个字符串 $S_1,S_2$ （小写字母前 18 个）， $n$ 个查询各给一个字符集合 $q$ 。问把 $S_1,S_2$ 中只保留属于 $q$ 的字符后得到的新串是否相等，输出 Y/N。

正解

怚路

1. 过滤串 = 逐字符计数对比

过滤后两串相等 $\iff$ 对每个字符 $c\in q$ ， $S_1$ 、 $S_2$ 中 $c$ 的出现次数与出现次序都一致。仅比计数不够（次序也重要），但把「保留字符的序列」逐段对比等价于：对每个字符 $c$ ， $S_1$ 与 $S_2$ 中 $c$ 的出现位置序列逐对匹配，且不同字符的相对次序一致。

实用做法：给每个字符分配随机哈希权重，定义前缀哈希 $H[i]$ = 串前缀中保留字符的加权和；查询时只累加 $c\in q$ 的字符贡献 → 用每字符前缀计数表 $O(1)$ 得每个字符在过滤串中的个数，再对比过滤串的逐字符序列哈希（前缀计数直接给出第 $k$ 个 $c$ 的位置，从而对比两串第 $k$ 个 $c$ 是否同位）。

本实现采用：每字符位置分桶 + 前缀计数表（translate + accumulate 在 C 级建表），查询时按集合 $q$ 逐字符对比两串中该字符的出现序列（位置逐对相等），并用 18 位掩码遍历集合。

2. 复杂度

建表 $O(18\cdot|S|)$ ，单查询 $O(|q| + \text{出现次数})$ ，总量 $O(n\cdot|S|)$ 级别，字符表小（18）是本题关键。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int ALPHA=18;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr); string s1,s2; if(!(cin>>s1>>s2)) return 0; int n; cin>>n; vector<string> qs(n); for(int i=0;i<n;i++) cin>>qs[i]; vector<vector<int> > pos1(ALPHA),pos2(ALPHA); for(int i=0;i<(int)s1.size();i++) pos1[s1[i]-'a'].push_back(i); for(int i=0;i<(int)s2.size();i++) pos2[s2[i]-'a'].push_back(i); int bad_single=0; for(int c=0;c<ALPHA;c++) if(pos1[c].size()!=pos2[c].size()) bad_single|=1<<c; vector<vector<int> > pref1(ALPHA, vector<int>(s1.size()+1)), pref2(ALPHA, vector<int>(s2.size()+1)); for(int y=0;y<ALPHA;y++){for(int i=0;i<(int)s1.size();i++) pref1[y][i+1]=pref1[y][i]+(s1[i]-'a'==y); for(int i=0;i<(int)s2.size();i++) pref2[y][i+1]=pref2[y][i]+(s2[i]-'a'==y);} vector<int> bad_pair(ALPHA); for(int aa=0;aa<ALPHA;aa++) for(int bb=aa+1;bb<ALPHA;bb++){bool ok=pos1[aa].size()==pos2[aa].size() && pos1[bb].size()==pos2[bb].size(); if(ok){for(int i=0;i<(int)pos1[aa].size();i++) if(pref1[bb][pos1[aa][i]]!=pref2[bb][pos2[aa][i]]){ok=false;break;}} if(!ok){bad_pair[aa]|=1<<bb; bad_pair[bb]|=1<<aa;}} for(int qi=0;qi<n;qi++){int mask=0; for(int i=0;i<(int)qs[qi].size();i++) mask|=1<<(qs[qi][i]-'a'); int bad=mask&bad_single; while(mask && !bad){int bit=mask&-mask; mask^=bit; int c=__builtin_ctz(bit); bad=bad_pair[c]&mask;} cout<<(bad?'N':'Y');} cout<<'\n'; return 0;}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 16:46
# update_at: 2026-10-02 16:46

import sys
from array import array
from itertools import accumulate

ALPHA = 18  # 字符表只有前 18 个小写字母，一个字符集合正好装进 18 位掩码


def positions(s: bytes) -> list[list[int]]:
    """字符分桶：buckets[c] 是字符 c 在原串里的全部出现位置，下标天然递增。"""
    buckets: list[list[int]] = [[] for _ in range(ALPHA)]
    for i, ch in enumerate(s):
        buckets[ch - 97].append(i)
    return buckets


def prefix_counts(s: bytes) -> list[array]:
    """字符前缀个数表：pref[y][i] = 字符 y 在位置 i 之前出现的次数。

    用 translate 把「是否等于 y」翻译成 0/1 串，再用 accumulate 求前缀和，
    两步都在 C 语言级别完成，整张表 O(ALPHA * len(s)) 建好。
    """
    pref: list[array] = []
    for y in range(ALPHA):
        table = bytearray(256)
        table[y + 97] = 1  # 只把字符 y 映成 1，其余字符全映成 0
        counts = array('I', accumulate(s.translate(table)))  # counts[i] 数到位置 i（含）
        counts.insert(0, 0)  # 开头补 0，让 pref[y][i] 恰好是位置 i 之前的个数
        pref.append(counts)
    return pref


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    s1 = next(data)
    s2 = next(data)
    n = int(next(data))  # 询问次数
    queries = [next(data) for _ in range(n)]
    pos1, pos2 = positions(s1), positions(s2)

    # 单字符集合：某个字符在两边出现次数不同，只保留它就必然不等
    bad_single = 0
    for c in range(ALPHA):
        if len(pos1[c]) != len(pos2[c]):
            bad_single |= 1 << c

    # 二字符集合 {a,b}：只保留 a、b 后的子序列相等，当且仅当两边 a、b 次数
    # 分别相等，且「每个 a 前面有多少个 b」这一列数完全一致——
    # 这列数（非降、每项不超过 b 的总数）加 b 的总数能唯一还原该子序列。
    pref1, pref2 = prefix_counts(s1), prefix_counts(s2)
    bad_pair = [0] * ALPHA  # bad_pair[a]：与 a 组队后必不相等的字符集合（位掩码）
    for a in range(ALPHA):
        for b in range(a + 1, ALPHA):
            before1 = tuple(pref1[b][p] for p in pos1[a])  # 每个 a 前面的 b 个数
            before2 = tuple(pref2[b][p] for p in pos2[a])
            cnt_ok = len(pos1[a]) == len(pos2[a]) and len(pos1[b]) == len(pos2[b])
            if not cnt_ok or before1 != before2:
                bad_pair[a] |= 1 << b
                bad_pair[b] |= 1 << a

    out: list[str] = []
    for q in queries:
        mask = 0
        for ch in q:
            mask |= 1 << (ch - 97)
        # 每轮取走最低位 c：二元子集 {c,d} 只在 c 被取走的那一轮被检查一次，
        # 因此整个集合的坏对检查恰好是 O(|q|) 而不是 O(|q|^2)。
        bad = mask & bad_single
        while mask and not bad:
            bit = mask & -mask
            mask ^= bit
            bad = bad_pair[bit.bit_length() - 1] & mask
        out.append('N' if bad else 'Y')

    sys.stdout.write(''.join(out) + '\n')


if __name__ == "__main__":
    solve()

复杂度

时间复杂度：建表 $O(18|S|)$ ，查询均摊 $O(|S|)$ 。
空间复杂度： $O(18|S|)$ 。

总结

「按字符集合过滤后比较」= 逐字符序列对比；字符表小（18）时分桶 + 前缀计数是正解。
bytes.translate + accumulate 建 0/1 前缀和是 Python 提速的实用技巧（C 级循环）。
位掩码表示字符集合，遍历只看集合内字符。

目录

形式化题目

正解

怚路

1. 过滤串 = 逐字符计数对比

2. 复杂度

代码

复杂度

总结