[蓝桥杯 2015 国 B] 密文搜索

题意

给一段只含小写字母的文本，再给若干个长度为 8 的密码。

如果文本中某个长度为 8 的子串，经过重新排列后可以变成这个密码，就算匹配一次。

要求所有密码总共匹配了多少次。

思路

先看一个可以直接验证想法的朴素解：

cpp

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// brute.cpp：直接枚举每个长度为 8 的子串并比较计数，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

string s;
int n;

bool same_count(const string &a, const string &b) {
    int c1[26] = {0};
    int c2[26] = {0};
    for (int i = 0; i < 8; i++) {
        c1[a[i] - 'a']++;
        c2[b[i] - 'a']++;
    }
    for (int i = 0; i < 26; i++) {
        if (c1[i] != c2[i]) {
            return false;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> s;
    cin >> n;

    long long ans = 0;
    while (n--) {
        string t;
        cin >> t;
        for (int i = 0; i + 7 < (int) s.size(); i++) {
            string sub = s.substr(i, 8);
            if (same_count(sub, t)) {
                ans++;
            }
        }
    }

    cout << ans << '\n';
    return 0;
}

因为允许“任意排列后相同”，所以真正重要的不是字符顺序，而是：

每个字母分别出现了多少次

也就是说：

两个长度为 8 的串互为排列
当且仅当它们 26 个字母的出现次数完全一样

于是可以把每个串都压成一个“计数签名”。

做法分两步：

先对原文本中所有长度为 8 的子串做滑动窗口
把每个窗口的 26 维计数压成签名，统计它出现了多少次

之后每读一个密码：

统计它的 26 个字母出现次数
生成同样的签名
直接去表里查，这个签名出现了多少次

把这些次数累加起来就是答案。

因为窗口长度固定为 8，滑动窗口更新计数非常方便。

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

string s;
int n;

// 把 26 个字母出现次数拼成一个字符串签名，方便放进 map。
string build_key(const int cnt[]) {
    string key;
    for (int i = 0; i < 26; i++) {
        key += to_string(cnt[i]);
        key += '#';
    }
    return key;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> s;
    cin >> n;

    map<string, int> mp;
    int cnt[26] = {0};

    for (int i = 0; i < (int) s.size(); i++) {
        cnt[s[i] - 'a']++;
        if (i >= 8) {
            cnt[s[i - 8] - 'a']--;
        }
        if (i >= 7) {
            mp[build_key(cnt)]++;
        }
    }

    long long ans = 0;
    while (n--) {
        string t;
        cin >> t;
        int need[26] = {0};
        for (int i = 0; i < 8; i++) {
            need[t[i] - 'a']++;
        }
        ans += mp[build_key(need)];
    }

    cout << ans << '\n';
    return 0;
}

复杂度

设原串长度为 L，密码个数为 n。

滑动窗口一共处理 L 个字符，每次生成签名需要看 26 个字母，所以复杂度是 $O(26L)$ 。

每个密码同样需要统计 26 个字母并查询一次，复杂度是 $O(26n)$ 。

总复杂度可以看成 $O(L + n)$ ，常数是 26。

总结

这题的关键转换是：

“排列后相同”不看顺序，只看计数
固定长度为 8，适合滑动窗口
文本的所有窗口签名先统计出来，再统一回答查询

本质上是“滑动窗口 + 计数签名”的字符串题。

[蓝桥杯 2015 国 B] 密文搜索

目录

题意

思路

代码

复杂度

总结